After you get the Colress MCHN, go south through Route 21 to reach Seaside Cave.
Explore the Cave
To reach the exit of Seaside Cave, you need to be able to Surf. There is also an optional area where you will need to use Strength.
Go south to find Battle Girl Tia, who has a level 47 Heracross.
Go south from the Battle Girl and down the stairs to get a Full Restore. Then go west from the Battle Girl and jump down the ledge. Here you find PKMN Ranger Mikiko, who has a level 46 Vibrava and a level 46 Gligar. She gives you a Persim Berry when you win. Use your Dowsing Machine near her to find a hidden Blue Shard.
If you hop down the south ledge near the PKMN Ranger, you will find items and trainers, as well as an exit to Undella Bay, but you won't make any more progress through the cave that way. Hopping down the east edge near the PKMN Ranger allows you to proceed farther through the cave.
If you go south from the PKMN Ranger, you find a Dive Ball. Hop down the ledge to the south to find Johan, who has a level 46 Onix and a level 46 Lairon. He gives you a Persim Berry when you win.
South from the PKMN Ranger guy, there is Black Belt Rocky, who has four level 44 Roggenrolas that are all standing around him before the battle. Walk up to him and say Yes to fight him. After you defeat him, the exit here is no longer blocked. If you go through, you end up in Undella Bay, where you can Surf south and west to Undella Town. The Pokémon Center is pretty close to Seaside Cave if you want to heal up.
From where you encountered Rocky and the Roggenrolas, go north, then cross the bridge to the east of the PKMN Ranger. Then north and west to get back to where you fought the Battle Girl. Go west of her and then jump down the ledge, but then go down the ledge to the east.
Go down the stairs here. Go south and you will reach Black Belt Drago, who has a level 47 Scrafty.
Surf east from the black belt to get the Heart Scale on the island. Then Surf north until you reach land. To the left, there are some stairs going down to B1F, and to the right there are some stairs going up. B1F is optional, so if you just want to continue with the game, go up the stairs. The next section is about B1F, so skip that section if you don't feel like going there.
Seaside Cave B1F
First, go south, past the stairs, and follow the path to reach a Max Repel. Then go up the left-hand stairs and use Strength to push the boulder into the hole. Go right and down the stairs.
You'll encounter Battle Girl Maki, who has a level 47 Mienfoo. Go up the stairs to the right of the Battle Girl and push the boulder to the left. Then stand below the nearest boulder (to the right of a brown rock) and push that boulder up into the hole.
There is a boulder up above. Push it up, then to the right, into the hole. Push the next boulder down into the hole. After that, push the next boulder to the right, then up into the hole. Get the Rare Candy nearby. Then go up and push the boulder up twice, then right, into the hole.
Go up and take the small set of stairs down to reach Black Belt Rich, who has a level 47 Gurdurr.
Seaside Cave 1F
Go up the stairs behind Black Belt Rich to return to the upper floor. Go left and up some stairs to find TM06 Toxic.
Don't go south from where you got Toxic! It takes you to the beginning of the cave, and you'll have to go through the entire cave again to get back to where you were. Instead, go east from where you got Toxic, down the stairs, then hop down the ledge just before the stairs to B1F.
Now go up the stairs to the right. There is a strange-looking rock thing here, blocking the exit. Check on it. If you got the Colress MCHN in route 22, the strange-looking rock wakes up and reveals itself to be a Crustle. You have to fight it. Once you defeat it, the Colress MCHN breaks. But now you can go to the exit. But first, turn on your Dowsing Machine and get the Calcium north of you. Then exit the cave.
You'll be back in Route 21. Walk east to see the Plasma Frigate. Hugh shows up, then Marlon arrives and puts down a gangplank so you can walk onto the frigate. Marlon wants to stay neutral about Team Plasma, but since you're in trouble, he wanted to help out. But then he goes into Seaside Cave, leaving you and Hugh to deal with Team Plasma.
When you're ready, follow Hugh onto the Plasma Frigate.