Fourth Gym to Fifth Gym
Now that you won the 4th badge, go back to place where the women performed. Talk to the man inside and he will give you HM03 which is surf. Teach it to one of your pokemon and head west.
You will fight some trainers and see some new pokemon in the tall grass. Go west and then south until you get to another city. You will see a gym with no one in it. Go south and you will see a large body of water.
Surf in the water and head southeast. You will have to fight some trainers and they all use water pokemon, of course. Then you will reach an island. Heal your pokemon and fight the trainers in the gym. They all use fighting pokemon. Defeat the gym leader. When you get out of the gym, you will see a woman. Talk to her and she will give you HM04 which lets you use strength. Talk to the people on this island. One of them will give you the fly HM which is HM02.