Yes, it can fly. I just don't remember the episode. Hold on, checking sites.
Edit: Okay, it has been a long time since I watched these, so I can't back this up. But from information I've gathered, it happened either in the opening theme song, the first episode, or Mewtwo Strikes Back. Sorry this isn't more help to you, but the internet sucks at this kind of thing.
Oh, and Gyarados does appear as floating in the Pokemon Stadium Games. Now that I can put myself behind 100%.