After you defeat your Dad in the Petalburg Gym, you and Wally go together to Mauville City, where you can go east to Route 118.
Explore the Route
Go east and you can battle Aroma Lady Rose, who has Oddish and Roselia.
In the northeast part of the beach, there is a Stardust.
On the south part of the beach, you find Fisherman Wade, who has Carvanha.
East of that, there is Guitarist Dalton, who has Magnemite and Whismur.
Use your Dowsing Machine on the beach to find a hidden Heart Scale.
In the next route, you might want to have the Acro Bike so you can access all the areas. If you don't have it now, you can go back to Mauville to switch bikes.
Now use Surf to go across the water in Route 118. If you have a pokémon with you that knows Surf, just walk up to the water and check on it to start Surfing.
While Surfing, you can encounter Pelipper, Tentacool, and Wingull in this route.
Talk to the fisherman near the north end of this beach to get the Good Rod. Using the Good Rod in this route, you can catch Carvanha, Magikarp, and Tentacool.
Southeast of that fisherman, use your Dowsing Machine to find a hidden Iron on a rock.
Go southeast from there and you can battle Fisherman Barny, who has Carvanha and Gyarados.
Go east and then north onto the grass. You will find Steven. Watch the cut scene. The two of you will go to the Southern Island.
If you want to go back to route 118, just talk to Steven.
Go north until you see another cut scene. Team Magma/Aqua arrives! Refuse to leave, and you will have to battle them.
In Omega Ruby, you will be up against Team Magma Admin Courtney, who has Camerupt, and a Grunt who has Koffing.
In Alpha Sapphire, you have to battle Team Aqua Admin Matt, who has Sharpedo, and a Grunt who has Grimer.
Afterward, Steven heals your pokémon. Then, if you are playing Omega Ruby, Latios joins you. If you are playing Alpha Sapphire, Latias joins you. If you already have six pokémon in your party, you will be asked to move one of your current pokémon into a PC Box to make room for your new pokémon.
Your new pokémon is holding the Mega Stone that allows it to Mega Evolve.
Steven gives you a Mega Bracelet so you can Mega Evolve your pokémon.
About Mega Evolution
In order for a pokémon to Mega Evolve, it has to be holding the correct Evolution Stone. The Latios or Latias that you just received is holding its Evolution Stone, for example. There are other Evolution Stones for other pokémon that can be found in the Hoenn Region, as well as in the Kalos region of Pokémon X and Y. Some pokémon do not have Mega Evolution forms.
To perform Mega Evolution in battle, send out a pokémon that is holding its Evolution Stone, then tap "Mega Evolve" at the bottom of the screen and choose the move that you want your pokémon to use. Before your pokémon makes its move, it will Mega Evolve.
Pokémon that have Mega Evolved will stay in their evolved form until the end of the battle or until the pokémon faints.
Mega Evolved pokémon have higher stats, and in some cases their Ability changes. Some Mega Evolved pokémon are a different type from their original form.
Route 118, part 2
Afterward, the two of you are flown back to Route 118, and Steven departs.
The next time you check the notifications on your BuzzNav, you will receive the Eon Ticket, which you can show to your Dad in the Petalburg Gym to return to the Southern Island.
Go north onto the grass. If you have a pokémon with you that knows Cut, you can cut the trees to the west for a shortcut. Otherwise, you will need to go east through the very tall grass.
To the northeast, there are a few Sitrus Berry trees.
To the east, you can battle Bird Keeper Perry, who has a Pelipper.
East of the Bird Keeper, you can get a Hyper Potion.
South of there, you can battle Bird Keeper Chester, who has Swablu and Swellow.
To the east, you will find Delinquent Miley, who has Cacnea and Mightyena.
Also, if you battled Gabby and Ty in Route 111, you will encounter them again here. They now have Loudred and Magneton.
You can optionally go east to reach Route 123, where you can find rare berries. You won't be able to go all the way through Route 123 from here, though.
Otherwise, go north from the east side of Route 118, and you will reach Route 119.