I strongly recommend the dream journal idea as well, but not necessarily for the same reasons as others; what you’ll most likely find, should you stick with it, is the vast amount of detail contained in your dreams that you just haven’t been remembering. Typically, your journal will contain details from the last dream or last two dreams you had prior to waking (and usually with far fewer details from the next-to-last). I’ve noticed that I can have as many as five or six dreams in a typical eight (er, maybe ten) hour sleep period, depending on how soundly I’m sleeping. Few of them I can remember fully; even fewer are applicable to my daily life. Remember to write as much as you can in the journal as soon as you wake (keep it by your bed), and write something everyday, even if it’s only a statement that you couldn’t remember anything. In my experience, the journal does not help with the deja vu-esque experiences; out of hundreds of dreams detailed enough to consider, I’ve only had two I would characterize as eerily “precognitive”–but the events which the dreams seemed to fortell were not experienced with the deja-vu feeling, were not life-changing in nature, and the only reason I remembered the dreams during the events is because I had in fact written them down.
IMHO, dreams and deja vu are intimately connected, not in the sense that the latter are always effects of the former, but in the sense that they use the same mental suspension-of-disbelief mechanism. In your dream, rarely will you realize, not matter how absurd the events of the dream are, that you are dreaming; we all act in our dreams as if they are real. If you should become lucid (realize you are dreaming within the dream), it is all too easy to forget it and slip back into the normal dreaming mode. Often people have dreams which seem to be a continuation of other dreams, or dreams that repeat, and the effect of deja vu can be even more powerful in the dream than in real life. Engywook is right on the money: you never seem to be able to take advantage of the deja vu to predict what will happen next, even though what does happen next might still be experienced as deja vu.
Based on my experience, if dreams are meant to be precognitive, then I’m a really crappy psychic. So many dreams are so bizarre and yet so amazingly intense. My best guess is that they are simply another astonishing faculty of the brain that we have completely ignored–like a muscle which is never worked–and so the vast majority of our dreams are mental masturbations. Deja vu, for me, is a similar thing, but it’s simply too easy to write it off as a mental burp. Deja vu in dreams can be devastatingly intense, to the point of ego loss, where you’re constantly forced to question what is real, what is being percieved, and who is perceiving it. It pains one’s skeptical intellect to assign any importance to such random absurdity, but in as much as it is being experienced, it is real. And much of our waking reality is a result of actions or words that usually begin as thoughts, a process which we take completely for granted but which, when you really consider it, is truly magical. Dreams use the same basic currency–thought–and if they manifest in our lives as actual events, you have to wonder: is it really precognition or merely visualization?