It appears that Firefox doesn't even look at the contents of this header, it just stores it for later. You can put a nonsense string in the Last-Modified header (from the server to the browser), and the next time a browser tries to fetch the file, it'll send the exact same string back in a If-Modified-Since header (from the browser to the server). I used "The bananas in my cellar are still quite green" as a test value, which, I hope you agree, looks nothing like a date. And that is exactly what I got back.
As a result, it acts like a private cookie, but just for this one URL, not for the whole domain, and not even for the siblings of this URL on the same path.
I found Opera 9 apparently behaves the same.
Now, MSIE(7) and Safari are something else. MSIE does appear to look at the contents of this header, it simply drops it if it can't make a date out of it. The format it accepts is quite flexible, I sent it something that's close to ISO-formatted: 'YYYY-MM-DD HH24:MI:SS "GMT"', to put it in Oracle's date formatting terms (for example: '2008-06-05 12:34:56 GMT'). But what it sent back was not the same string, but a date string that is converted back to the http standard form: 'Dy, DD-Mon-YYYY HH24:MI:SS "GMT"' (for example: 'Thu, 05-Jun-2008 12:34:56 GMT')(which, BTW, doesn't make sense to me as a standard, looking at it from a date parsing point of view: it's too complex).
Safari takes this even one step further: if the header isn't a date in http standard form, then the header is simply dropped. It simply doesn't send an If- Modified-Since header on the next request.
But it is safe to say that if your date in the Last-Modified header is in http standard form, you will get the exact same string back in the If- Modified-Since header. No browser appears to change the value of the date. It doesn't matter if your clock is off, or you're in the wrong time zone... All that matters is that you'll get the exact same date string back as you sent out.
So, as a rule of thumb, how do I recommend using it? I am now feeling that you ought not try to convert the date back to seconds-since-epoch, or whatever internal format you may be using, and next compare it to the file modification date. Instead, you ought to convert the file modification date to a standard http date string, and compare this string to the If-Modified-Since header. If it's the exact same string, then you may safely send out a "304 Not Modified" header and not much else (no body). If it's a different string, then send the whole file, headers and body, again.
It doesn't matter if your clock is off. All that matters, is that you must be consistent, and always format the same date/time into the same string. And then, it'll just work.
Note that using this scheme, it'll also send out the body if the Last-Modified header is technically later than the date in the If-Modified-Since header. That' s not bad, instead, it's better: all too often I find that someone replaced a file on a webserver with a copy of an older file, and if you do check which date is the latest, then you will miss this change.