This can be quite a dry subject, and so this entry is an attempt to make it as light as possible. It might have mixed success, but onwards, anyway!
Omniscient means 'all knowing'. If God is omniscient, He knows everything there is to know. However, if God truly does know everything, certain problems arise. These problems, however, are different depending on which definition of omniscience you use.
A Timeless Omniscient God
God is timeless, and therefore outside of time. If God is 'outside' time, it means He sees the past, present and future at the same 'time'1. Peter Vardy, the Catholic writer of many useful books, provides the analogy of God sitting on a mountain, looking down on the stream of time, seeing the mouth and the source all at once. Time doesn't pass for God because all time is present to God simultaneously.
A timeless God's knowledge can therefore be seen as omniscient: a timeless God knows everything, past, present and future, in every detail. Yet this raises a big problem! If God knows everything about our future, how exactly are we free?
This has been implied in Christianity with predestination. This theory finds our lives to be determined by God, which is incompatible with human free will. However, God is supposed to have given us freedom, a gift to turn away, or towards Him. Yet, if our actions are wholly determined and controlled by God, then we cannot be free. If timeless God knows our future, then we can only live one life, and how does this make us free?
Boethius tried to address this problem. He was a consul in ancient Rome, and wrote the Consolation of Philosophy, while in prison. He created a character, the 'Lady Philosophy', to strike up a dialogue for his book. He put to the Lady, that God knows everything, and therefore He knows humanity's future actions, and thus we aren't free. The Lady Philosophy responds that he is mistaken. God does timelessly know what happens in the future, but this knowledge is not causal. God sees our future free actions, but what He sees is the result of our freedom - God doesn't cause us to act in a particular manner.
Therefore, God knows all human actions, past, present, and future, without taking away human freedom. Our free actions are what God sees, yet His knowledge doesn't cause us to act in one way or another.
The Everlasting Omniscient God
With an everlasting God, unlike a timeless God, He is inside time. To the everlasting God, the future is the future, and the past is the past2. God has complete access to the past, and to the present, but a problem arises with His knowledge of the future.
An everlasting God has only limited knowledge of the future, He knows future events that depend on the present situation, such as the date that Halley's Comet will reappear in our Solar System. Yet, can an everlasting God know the future free actions of humanity? This depends upon how we define freedom:
This is the freedom to act according to our own choices, in ways not determined by our environment or genetics. This freedom is restricted by the laws of the universe (you try flying and see where it gets you!). God doesn't know the future free actions of humanity, as there is no truth to be known. God may be able to predict, yet He can be mistaken (as Little Jimmy in the third row pipes up, 'but I thought God was perfect!'). God's omniscience cannot extend to the future actions of humanity.
Therefore, an everlasting God is still omniscient because He knows everything that it is logically possible to know. The major problem with this perspective is that it restricts God's knowledge: He didn't know about the Holocaust before it happened, or what will happen tomorrow.
Freedom to Act According to Our Nature
If 'freedom' is freedom to act in accordance to our nature, then humans are free to do whatever they wish, yet what they wish is determined by our nature and nurture. ('but how can we be free if...' 'Shut up Little Jimmy!') In this way, if someone is hypnotised to act in a certain way, that person by this definition is still free to act in accordance with his or her nature, even if that nature is determined by the hypnotist. We would think ourselves to be free but would not be able to choose alternative courses of action. If we have this freedom, then the everlasting God would know, in the present, future 'free' actions, because these actions are determined by our nature. (On a pointless aside, this is called compatibilism, which Kant called a 'miserable subterfuge', so as you can guess that he really liked it).
The view of God as everlasting has its merits, because it emphasises God's personality. He knew the possibility of various atrocities, yet could not have interfered without compromising human freedom.
There is more discussion of this and related topics in the entry on Free Will versus Determinism.