After training up in Celestial Tower, you should go to the Mistralton Gym and battle Skyla for the Jet Badge.
Through the Gym
Talk to Clyde to get your Fresh Water.
There are powerful fans blowing in this gym, and you have to hold the B button to run quickly enough to avoid being pushed around. You can also stand on green tiles with walls to avoid the wind.
Go up and stay behind the wall. Wait for a big gust of wind, then go to the safe green tiles to the right.
Now go around the wall to the Pilot to the north. It's Pilot Flynn, who sends out a level 37 Swoobat. After the battle, make sure you are above the wall that you hid behind a moment ago. The gust of wind will just push you up against the wall.
Wait for a gust of wind, then immediately run north and get into the next walled area. After the next gust of wind, immediately run south to the next walled area. After that, go southwest to the next walled area.
The pilot down here is Pilot Winslow, who has a level 37 Sigilyph. After the battle, go back up to the walled area. After the next gust of wind, quickly run north and east to the next walled area.
The next walled area is north, and there's a Pilot hiding out in it. He's Pilot Elron, and he has a level 36 Archen and a level 36 Unfezant.
Go east to try to make it to the next walled area. If the wind gets you before you reach the next area, you'll fight a pilot with a level 37 Unfezant. Then go east to the walled area.
From this area, go north and west and hide out in the walled area. The path here splits into three. The lower path is the correct one. The pilot here has a level 36 Ducklett and a level 36 Swoobat. Go north from him to reach Skyla.
Skyla has a level 37 Swoobat, a level 37 Skarmory, and a level 39 Swanna.
When you win, you get the Jet Badge, and TM62 Acrobatics.
Go south from Skyla to exit the gym. Outside, Professor Juniper will come over and ask you to come with her on Skyla's plane to Lentimas Town.