After you explore Veilstone City and meet Dawn or Lucas, you can enter the Veilstone Gym to get your third Gym Badge.
North of the entrance, you can battle Black Belt Jeffery, who has a level 26 Machoke and a level 26 Meditite. You get 832 Pokédollars for winning.
In the southwest of the gym, you can battle Black Belt Darren, who has two level 25 Machokes and a level 25 Machop. You get 900 Pokédollars for winning.
In the southeast of the gym, you can battle Black Belt Rafael, who has a level 28 Meditite. You get 896 Pokédollars for winning.
Go north from the middle and you can battle Black Belt Colby, who has three level 25 Machokes. You get 900 Pokédollars for winning.
To reach the Gym Leader, you will need to push the yellow walls to open the path. First, go to the southeast Black Belt and push the yellow wall in his room to the right. Then go north up the stairs in his room to reach the empty room to the north. Push the first yellow wall in that room to the right. Then go to the southeast corner of the gym, and from there you can now go north through the two walls that you pushed. At the top, push the northernmost wall to the left.
Next, go back to the southeast corner of the gym, and go north up the path between the east room and the middle room. Push right on the wall in your way, then go north and push right on the wall there.
Go back to the east side of the gym and push left on the wall north of the Black Belt. Then go into that Black Belt's room and go north until you reach the north end of the gym. Go to the left and push left on the wall there. Then go east and make your way south through the two rooms.
Go to the northwest corner of the gym and push right on the wall there. Then go into the middle Black Belt's room and push left on the wall there. Go north from there and push left on the next wall. Then go northwest and push left on the wall. Then go south through the middle Black Belt's room and go up the path between the middle Black Belt's room and the southwest Black Belt's room. Push left on the wall there.
Go to the southwest corner of the gym and push right on the wall there. Then go north through the southwest Black Belt's room. At the north end of the gym push right on the wall at the top.
Go east and then south until you can go east again, then go north through the northern Black Belt's room to reach the Gym Leader.
Gym Leader Maylene
Maylene has a level 27 Meditite, a level 27 Machoke, and a level 30 Lucario. You get 3840 Pokédollars for winning.
After you get the Cobble Badge, you can use Fly outside of battle. You also get the Stickers that Maylene uses, and some TM60s, which teach Drain Punch.
Help Dawn or Lucas
When you go outside, Dawn or Lucas will ask for your help. Go to the warehouse in the northwest of Veilstone City and talk to Dawn or Lucas. You will battle two Team Galactic Grunts together. They have a level 25 Dustox, a level 25 Beautifly, a level 25 Croagunk, and a level 25 Stunky. You get 2600 Pokédollars for winning.
Go east and then north to enter the warehouse. Go northeast from the warehouse entrance to find TM94 Fly. This will unlock it in your Pokétch, allowing you to instantly fly to places that you have visited before. You can also fly using the Town Map.
When you are ready to move on, go south to Route 214.