From StrategyWiki, the free strategy guide and walkthrough wiki

Now that you know Surf, you'll get an opportunity to capture Pokémon, gather items and battle trainers.

• Swimmer Dawn
  • Marill (lvl. 27)

• Swimmer Beverly
  • Wailmer (lvl. 26)
  • Wailmer (lvl. 26)

On the western edge of this waterway, you'll encounter a long vertical island. Search it to find a trainer.

• Ruin Maniac Foster
  • Sandshrew (lvl. 26)
  • Sandslash (lvl. 26)

Once you beat Foster, Surf on the west side of this island. Beat this trainer:

• Swimmer Austin
  • Magikarp (lvl. 25)
  • Tentacool (lvl. 25)
  • Wingull (lvl. 25)

Surf up to the rock formation to the north, this one will turn into a cave (Island Cave) when you decipher the message in the Sealed Chamber. Make sure to return here. For now, continue south. At the southern tip of the island is a trainer.

• Swimmer Luis
  • Carvanha (lvl. 27)

Surf south, sticking to the western rocks. Search the islands to find an Iron. Then continue south to Route 106.