If I start to thank Him, He already knows that for which I'm thanking Him - and He knows that I'm thankful for it. If I confess my sins to Him, He already knows them. If I ask Him for anything, He already knows my request. Why bother talking to Him at all, if He already has gotten the message before I think it?
There is possibly more than one correct answer to this question. The first might be obedience: we pray because He tells us to do so.
Another possible solution to the paradox of prayer is located on the borderline between psychology and spirituality. There is a cleansing effect to a conversation with an omniscient being, if we have meditated on the listener's omniscience. All possibility of pretense is removed.
I cannot pray, "Dear Lord, I want to be a better person," if in fact the personal sacrifices required to be a better person are ones I don't wish to make; I might pray, "I know that I should be a better person, but I really don't want to give up some particular pleasure." This admission can be the first step in God's work of improving me when I can't improve myself.
If I approach the searching light of God's omniscience with a request, I am forced to ponder, not the obvious fact that I want this or that, but rather why I want it; He can see my motives. I am also led to consider whether there might be something better than what I am requesting - an omniscient being will know better than I what all the options are, and what the unintended consequences of granting them can be.
When I confess my sins, He knows my darkest thoughts, and how I can be complacent with myself. His investigation moves effortlessly through the facade I've carefully built - a facade designed to convince myself and others that I'm a pretty decent human being.
When God says, "Be still and know that I am God," (Psalm 46) perhaps this is part of the meaning behind it: that a meditative stillness in the face of His omniscience is an important part of prayer. To stop talking to Him for a bit, and simply realize that I am thoroughly known. His act of knowing us can change us - Christians over the centuries have variously rephrased the truth that one benefit of prayer is to change the character of the one who prays.
It is, in any case, an amazing thing to have a conversation with someone who knows everything.
