After going through Route 104 and the Petalburg Woods, you reach Rustboro City, where the Roxanne's Rock-type Gym awaits.
Battle Roxanne
After you heal up and buy supplies, you should go into the Rustboro Gym to battle Roxanne.
After the Gym
After you get the Stone Badge, leave the Gym and go west. You will see that a Team Aqua/Magma Grunt has stolen a Devon Researcher's goods.
To the west of the Pokémon Center, there is a house with a sign out front that says Cutter's House. Go in and talk to the man to get HM01 Cut. You can use an HM as many times as you want. It never disappears. Cut is a Normal-type move, so you might want to teach it to a Normal-type pokémon like Zigzagoon because when a pokémon uses a move that is the same type as the pokémon itself, that move is stronger than if it were used by a pokémon of a different type. So a Normal-type pokémon's Normal-type moves are stronger, and a Water-type pokémon's Water-type moves are stronger, and so on.
If you teach a pokémon Cut, you can go back to Route 104 and use Cut on the tree that is southeast of the bridge. You can get the X Accuracy after cutting down the tree.
Similarly, you can go back to Petalburg Woods and cut the trees in the northeast area, then explore the eastern side of the woods and get items there that you couldn't reach before. Just past the grass east of the small trees, there is a small area to the north. Check that area to find a hidden Tiny Mushroom. Go east and talk to the girl to get a Miracle Seed. Go to the northeast area to get a Great Ball. Go south from there until you have jumped down two ledges. Go to the south edge of the grass and check on the empty patch of grass to the left to find a hidden Tiny Mushroom. Then go northwest to find an X Attack.
When you're ready, go back to Rustboro City and finish exploring there, then go north to to Route 115. You can't access the whole route right now, but if you go west to the beach, then follow the beach north and east, you will find a Super Potion at the end of the beach. After that, go back to Rustboro City.
Go to the northeast part of the city and you will find the Devon Worker whose goods were stolen. The Devon Worker says that the Team Aqua/Magma Grunt went east, so go east to reach Route 116.