After you Surf through Route 124 to reach Mossdeep City, you can enter the Mossdeep Gym to challenge the Psychic-type trainers there.
Prepare
The trainers in this Gym have Psychic-type pokémon, which are weak to Bug, Ghost, and Dark attacks. Dark-type pokémon are immune to Psychic attacks, making them ideal for this gym. Psychic-type pokémon are strong against Fighting and Psychic attacks. Fighting-type and Poison-type pokémon are weak to Psychic attacks, so don't bring those types to this gym unless they are also Dark type (making them immune to Psychic attacks). Some of the trainers here have pokémon that know Fighting, Rock, Grass, Normal, and Dark attacks in addition to Psychic attacks, so keep that in mind when choosing pokémon to bring with you.
Battle Trainers
From the entrance to the gym, go up and step on the white dot. You will float to the platform with the first trainer. This is Psychic Preston, who has a level 42 Kadabra. Check on the rock to the left of Preston to change the white dot paths. Then go south and step on the white dot to go back to the entrance platform.
After that, go north and step on the white dot to be sent to the next platform. This trainer is Psychic Joshua, who has a level 40 Kadabra and level 40 Medicham. Check on the rock on the right side of this platform to change the paths.
There are now two paths to choose from. Going south leads you to an optional battle with Hex Maniac Kindra, who has a level 39 Kirlia and level 39 Grumpig.
Go east to battle Psychic Fritz, who has a level 39 Claydol and level 41 Starmie. Afterward, check on the glowing rock to open the next path.
This opens two paths to the left. The upper one leads to Hex Maniac Kindra, whom you might already have battled.
The lower path leads to the northwest platform, where you can battle Hex Maniac Patricia. She has a level 41 Chimecho.
Check on the rock near Patricia to change the paths. Now you can go southeast for an optional battle with Psychic Virgil, who has a level 40 Kadabra and level 40 Girafarig, or you can go southwest to return to the entrance of the gym, where you can go north to reach Gym Leaders Liza and Tate.
Liza and Tate
Liza and Tate challenge you to a Double Battle. They have a level 45 Lunatone and level 45 Solrock.
Both of these pokémon have the Levitate ability, making them immune to Ground attacks.
The Lunatone has a Psychic attack and can also inflict Sleep on your pokémon, so you might want to equip your pokémon with Pecha Berries. The Lunatone also knows Light Screen, which will cause its Special attack to double if you hit it with a Special attack while Light Screen is still in effect.
The Solrock knows a Grass attack, Rock attack, and Psychic attack. In addition, it can use Sunny Day, which allows it to use its Grass attack every turn instead of every other turn. Sunny Day also weakens Water attacks.
After you Win
After you defeat Liza and Tate, you get the Mind Badge, which makes traded pokémon up to level 80 obey you. It also allows you to use Dive outside of battle, which will allow you to go underwater in certain areas.
You also receive TM04 Calm Mind, which increases Special Attack and Special Defense.
Step on the glowing spot to the right of the twins to leave the gym.
Watch the cutscene when you go outside. After seeing a disturbance in Route 128, Steven gives you HM07 Dive, and the Devon Scuba Gear.
After you teach Dive to a pokémon, you will be able to go underwater if you Surf onto dark water and press A. This opens up many optional places to explore. To find these optional areas, look for dark water in Route 107, Sea Mauville (north of Route 108), Route 124, Route 125, and Shoal Cave (north of Route 125).
The next gym will be a Water-type gym, so start training your Grass and Electric pokémon now.
When you are ready to continue with the story, go south from Mossdeep City to reach Route 127.