As Sempiternus mentioned, Gyarados is based on a Chinese mythological dragon 龙 (NOT sea serpent 蛟).
The story goes that carps 鲤鱼 living in the Yellow River 黄河 swam against the current in a bid to reach Dragon's Gate 龙门 (in Sichuan province) as it was said to be a wondrous place. However, in their way lies a mountain 龙门山 which they, having no legs, cannot scale. Thus it was that some carps tried swimming up the waterfall, but invariably most got flushed right down. They then tried leaping out of the water, but many still fell and even got bruises as a result (that is why carps found in the yellow river often have black spots on the head).
Only the few that truly persevered managed the feat of leaping all the way through Dragon's Gate, and as a reward were turned into dragons. This is where the phrase 鲤鱼跳龙门 comes from, to mean that through perseverance one can reach great heights previously thought un-achievable (mainly applied to work or business).
So why can Gyarados fly without any visible wings? Because that is what Chinese dragons do.
Unlike the European ones, Chinese dragons are always associated with water (as opposed to fire). And this includes water from the skies - rain. Despite only having at most claws, they slither through the air and are the gods in charge of bringing down rain and storms. That is why Gyarados, being a Chinese dragon, doesn't need wings to move through the skies. It also explains the Pokemon's close association with hurricanes and storms.
Also, the dragon is closely associated with the Chinese Emperor, who is also known as the son of heaven 天子. Therefore both the skies (flying) and the seas (water) would be appropriate elements to associate with Gyarados.