After Colress gives you the Colress MCHN on Route 22, you should go south through Humilau City and continue south to Route 21.

Explore the Route

You need to use Surf south of Humilau's pokémon center to reach Route 21.

Shortly after entering the route, you find Swimmer Desiree, who has a level 46 Wailord.

Southwest of her, you find Swimmer Harold who has a level 46 Octillery. If you go southeast from Swimmer Desiree instead, you find Swimmer Kaoru, who has two level 45 Remoraids.

Directly south from Swimmer Desiree, there is some shallow water where you can get a Big Pearl. Just east of this shallow water, Swimmer Kyle is going in circles. He has two level 45 Wingulls.

Southwest from the Big Pearl, you find Black Belt Kenneth, who has a level 47 Crustle.

Now go back to where the Big Pearl was, then go east and south until you reach the beach. Walk west on the beach. Next to the cave entrance, you find Doctor Braid, who has a level 46 Alomomola. After you beat him, he'll heal up your pokémon for free.

Walk west between the trees and battle Fisherman Kenzo, who has three level 44 Frillish. Go south of the Fisherman to get a PP Up.

Now go back to the cave entrance next to the Doctor. Go inside to reach Seaside Cave.