Once you leave the floating continent you'll want to find a ship wrecked in the middle of the ocean. It's kind of hard to describe where it is, but if you go towards the island with the temple, and then south to where the Sylx Tower sticks out of the water and then go south-westish. You should find it there. Yes, it is in the middle of nowhere. No, there's no dialogue or any indication that that's where you have to go next. Such is the way of old-school RPG's. Psychic ability is 30% of the skill involved, next to persistence.

You'll get the Karateka once you've done all the jazz involving the water crystal, and he's a notable improvement over the monk. Infact, it's not unfeasible to keep your main melee attackers as Karateka until you get Ninjas/need Dark Knights to get through the cave with splitting monsters.