I found it, when you reach Cianwood City across the sea, you will find a lady walking in front of the gym there. She happens to be the gym leader's wife. She will tell you that it is much easier to cross the sea by flying, but she wont let you have it unless you beat the gym. Beat the gym there and come back to talk to her; she will then give you HM2-FLY.
You can teach Fly to Togetic, the egg the daycare people gave you hatches into Togepi; its evolved form (Togetic) can learn Fly.