After exploring Route 128, you go underwater and discover a cave where the stolen submarine is hidden. Above it, you find Seafloor Cavern.
In this area, you can encounter Zubat and Golbat. While Surfing, you can encounter Zubat, Golbat, and Tentacool. With the Old Rod, you can catch Tentacool and Magikarp. With the Good Rod, you can catch Tentacool, Magikarp, and Wailmer. With the Super Rod, you will find Wailmer.
Explore the Cave
From the room where you entered, go north and into the cave entrance.
In this room, go north and use Rock Smash on the jagged rock. Then push the nearby round rock up or down. Then go to the right and push that round rock to the right. From there, go north.
There is a Grunt up here. In Ruby, he has Poochyena and Numel. In Sapphire and Emerald, he has Poochyena and Carvanha.
At this point, you can choose to either go northwest, or go east up the stairs. If you go east, you will be going the long way through the cave, where you can battle more grunts. If you go northwest, you will be going the short way, with fewer grunts to battle. If you want to go the short way, skip the next section.
The Long Way
After battling the first grunt, go east and up the stairs. You'll pass by a grunt who, in Ruby, has Numel, and in Sapphire and Emerald, has Carvanha.
Go south after that and go through the door. If you go southeast, you can battle a trainer later, but if you go southwest, you can skip that trainer. If you decide to go southeast, push the upper rock to the right, then push the lower rock down, then use Rock Smash on the jagged rock. Go through the door, go south, and battle the trainer there. Otherwise, if you go southwest instead, push the rightmost rock down, then use Rock Smash on the jagged rock. Then go through the door.
Go northeast and through the cave door there. In the following room, go up and push the first rock up, then go to the left and push the next rock to the right. Then go up and push that rock up. Use Rock Smash on the nearby jagged rock, then go past where that rock was, and push the next rock to the right. Then go north and go through the door.
In the next room, Surf in the water and go to the bottom wall, then go to the right over the small current that is flowing to the right. Keep going right into the next current. It will push you up. Go up again. The current will push you left. Go up and get into the current that is flowing to the right. It will push you to the upper-left part of the room. From there, go to the left and Surf up to reach a door. Go through that door.
The Short Way
After battling the first grunt, go northwest through the door. Go north and push the rock up, then go to the right and push the next rock up. From there, go left and push the next rock left. Use Rock Smash on the nearby jagged rock, then go north and push the next rock up. Go to the left and use Rock Smash on the jagged rock, then push the nearby rock to the left. Go up and through the door.
Surf north into the flowing current, then when you stop, go to the right. The next time you stop, go to the right. After that, go to the left. From there, surf north to the next door.
After following the instructions in one of the two previous sections, you should be in a room with many rocks that you can push with Strength.
First, if there is a ledge in front of you, push the first rock up once, then left once. If not, just skip to the next paragraph.
Push the bottom-right rock to the right. Then there should be a rock above you that you haven't pushed yet. Push it to the left. There is a rock above the one that you just pushed. Push it to the left. Next, go up and push the top-middle rock down. Finally, push the upper-right rock to the right.
Go north from there and you have to fight Magma Admin Courtney in Ruby or Aqua Admin Shelley in Sapphire and Emerald. Courtney has Camerupt and Mightyena. Shelley has Sharpedo and Mightyena. After you defeat her, go north and through the door.
Another Rock Puzzle
After defeating the Aqua/Magma Admin, you find another rock puzzle in the next room. First, push up the middle rock. Then push the left rock left, and the right rock right. Next, push the bottom middle rock to the left (this is the rock that you pushed first). Then, push the upper-middle rock up. Go to the rock that was to the right of it, and push it right, and go to the rock that was to the left of it, and push it left. Then push the upper-right rock up, and push the upper-left rock up. Then push the upper-middle rock to the left. Now you can go through the north exit.
You find yourself in a room full of mist. Go east to find TM26 Earthquake. Then follow the path through the room and you will see a cutscene. Then you have to battle Maxie if you are playing Ruby, or Archie if you are playing Sapphire or Emerald. Maxie has Mightyena, Crobat, and Camerupt, while Archie has Mightyena, Crobat, and Sharpedo.
Afterward, you have to go to Sootopolis City. To get there, go west from Mossdeep City, then go south to Route 126, and Dive there to find the cave entrance in the southern underwater area.