Sootopolis is accessible as soon as you learn Dive, but to challenge the gym leader, you must first complete the tasks at Cave of Origin.
It is an ordinary city in Hoenn with quite a few features, and where you obtain your final badge. It is only reached by diving or flying. Wallace is the gym leader in this town for Pokémon Ruby/Sapphire and Juan is the gym leader in this town for Emerald. In Ruby and Sapphire, Barboach and Shroomish can be shown to the residents and will hand out and Ether and Elixir respectively. In Emerald, Seedot and Lotad must be shown to the residents instead. This is the only place to get certain Poké Balls.
Traverse through the left path to reach Steven Stone. After he notices you, he will greet you and show you to Wallace, who will then lead you to the Cave of Origin. You must complete the cave to gain access to the Gym.
This gym is packed with trainers using Water- and Ice-types, so your best bet is to use Electric-, Grass-, Rock- and Fighting-type moves. Additionally, there's multiple puzzles where you have to step on all the ice, but a single piece breaks if you step twice on it, so watch your step!
The first puzzle is easy enough. Move in a S-shape, and you've done it. If you fall down at this stage, there'll be some trainers waiting for you below. From top to bottom, they are:
For the next puzzle, stay to the left wall until you're past the rock, then loop back on yourself and move along the lower path to get to the right wall, then move across the top. The trainers below are:
For the third and final puzzle, start by moving 2 spaces right. Move 1 space up and another 2 right. Move 1 space down, then 1 right, then 3 up. Move 2 spaces to the left, then 1 down, then 1 left, then 1 up, then 1 left, then 2 down. Move 2 spaces left, then 1 down, 1 left, 1 up, 1 left, 1 down, 1 left, 1 up, 1 left. Finally, move 2 up, 1 right, 1 down, 1 right, 1 up, 1 right, 1 down, 1 right, 1 up, 1 right. Now, all that's left (after the trainers) is the Gym Leader, Wallace.
The Luvdisc is not a threat, as long as you don't allow it to confuse you. His Whiscash is a much bigger problem. It knows Earthquake, so any Electric-type Pokémon will be at a disadvantage. It's better to swap to a Grass-type and faint it that way. While Sealeo does have a move to boost Special Defense, it's 2-shot by most Electric- and Grass-type moves at this level anyway, so it doesn't matter. Seaking has Aurora Beam, which will put your Pokémon in the red or, in the worst cases, faint it altogether. Make sure to bring a Pokémon with enough Special Defense to tank one or two and you should be fine. Finally, there's his Milotic. It knows Ice Beam to one-shot any Grass-type you have, Water Pulse to deal general damage, and Recover to regain lost health. Your best bet is to hit with a powerful Electric-type move before it has a chance to use Ice Beam and faint you. On top of that, Wallace has 2 Hyper Potions to give to his Pokémon, making the fight even harder.
Your reward for defeating Wallace/Juan is 4300/4600 Pokédollars, the Rain Badge, the ability to fully control Pokémon of any level, the ability to use the HM07 (Waterfall) outside of battle, and TM03 (Water Pulse). Congratulations, you have beaten every Gym in Hoenn!
Now all that's left to do is go to Ever Grande City and challenge the Elite Four. But first, some sightseeing!
Magikarp
Tentacool
Gyarados