http://en.wikipedia.org/wiki/Deja_Vu
"Scientifically speaking, the most likely explanation of déjà vu is not that it is an act of "precognition" or "prophecy," but rather that it is an anomaly of memory giving the impression that an experience is "being recalled.""
I don't think the bit about the one eye receiving information slightly faster than the other has any credibility though, since I'm blind in my left eye and get Deja Vu all the time.
Theories I've heard:
Your brain lags behind your senses so it feels like it's already happened because it has. Doesn't make sense to me since you can experience Deja Vu in real time while doing something like driving or other difficult tasks requiring specific timing.
Your brain bypasses putting the event into short term memory and puts it straight into long term memory, so as you recall it (immediately) it feels like it happened before. This one sounds the most plausible of all the theories I've heard.