Dictionary.com said:
fly /fla/ Pronunciation Key - Show Spelled Pronunciation[flahy] Pronunciation Key - Show IPA Pronunciation verb, flew or, for 11, 19, flied, flown, flying, noun, plural flies.
–verb (used without object)
1. to move through the air using wings.
2. to be carried through the air by the wind or any other force or agency: bits of paper flying about.
3. to float or flutter in the air: flags flying in the breeze.
There are over 30 more definitions. Many, if not most, of them mention air. A few mention the vaccuum of space. None mention water, or any other liquid. Flight, or more precisely, a fly speed, is defined in D&D as describing the ability to move through air. The particular body parts used (or not used) and the particular motions used (or not used) and the magic (or lack of magic) involved are NOT important.
What IS important is the medium through or along which the movement is made.
For flying (fly speed), it is air.
For walking/running (land, or normal speed), it is ground (regardless of whether there is air or water or chicken soup above the ground... "firm footing" is involved).
For swimming (swim speed), it is water.
For burrowing (burrow speed), it is loose earth (and yes, burrowing animals do push earth out of the way with their heads...see draconomicon).
For climbing (climb speed), it is branches/stone handholds & footholds/rope/etc.
A bird moving it's limbs about and directing it's movement through water is swimming, not flying. Because the movements of it's wings do not constitute flying. The propulsive effect of those movements in air constitute flying. In water, if those motions produce propulsion, they constitute swimming... in earth, burrowing, etc.
I think it is logically far more reasonable (given the most common usage patterns of the words) to extend the notion of flight to other gaseous mediums, swimming to other liquid mediums, and burrowing to other solid aggregates of similar consistency to loose earth.
Artoomis, to a certain extent, I agree that you can use common sense to extend a bit when confronted with rule text that is not explicitly exclusionary (though I tend to lean towards the belief that if a rules says.. ability X can do A, B, C, and D in these circumstances... then ability X, by default can't do G). However, is this case, as I have stated above... I think common sense and English usage point towards movement through air (or matter in gaseous form, more generally) to be the most proper meaning for fly... and similarly movement through water (...liquid..) for swim.
The rules also cover very well what to do with creatures who do not have a swim speed and do not automatically sink or float based on bouyancy. They make swim skill checks to move at some fraction of their base (land) speed.
So, movement in water is either based off of swim speed or a fraction of land speed for those creatures not possessing a swim speed.... strictly RAW, of course.
Many of the suggestions in this thread, from the FAQ, or even in trying to extend the MotP rule for the Plane of Water to the Prime Material produce workable, sensible "solutions" for people that don't feel that the RAW properly models their notion of what the fly spell should do. That's fine. I'm not even saying I wouldn't make a similar ruling. However, in my view, it would clearly be contradictory to RAW.