How and when did the water come into being? In Genesis 1:2, the Spirit of God is hovering over the face of the waters.

So this is before creation, so where does water come from? why it exist before the first day? And if there is face of water, there seems to me should be some gravity somewhere, what's the stage of universe at this time?
Well, you see, when two atoms of hydrogen love an atom of oxygen very much...

When I was a literalist (and it seems you are looking through those glasses) my interpretation was that when God created the heavens and the earth (Gen. 1:1, "In the beginning, God created the heavens and the earth."), that would have included the waters. Since the waters and the lands and the waters above the heavens and the waters on the earth were not separated yet, then it is a bit difficult to nail down the dimensionality of it all, but simply because we cannot conceive of a world where there is little boundary between gaseous and liquid state that does not means that it could not exist. Of course, fog exists, so it is quite possible that water was originally created as a liquid suspended in air.

You might be reading too much into "over". To say that God is literally and exclusively "over" something is as nonsensical as saying he is literally and exclusively "under" something. Time and space are never literal in such a context.