The shops here have the same stuff as in the Empire, and none of the townspeople here really give you any good clues about how to get a boat.
What you need to do is to approach the goose at the end of the pier, and say "No." This will launch a boss battle.
Kracken can use Gigavolt, which can kill a party member in one blow. So, either leave them be, revive them, or just let him kill your whole party, and then watch a video to get revived and continue the battle. (I know that's not an effective strategy, but hey - it works...)
Anyway, have Blont, Bruce and Linn attack, have Mazenda use Fire, and have Temi either Cure or attack as necessary.
After this battle, talk to the Captain, and he'll give you his boat. Now, walk onto the goose and sail it out of the harbor, and now you can use your boat on the World Map!
Note: Your boat will warp with you any time you use the Warp spell. Usually it'll be easy to find, but sometimes you might have to hunt around a bit. However, it will always appear along the coast, close to whichever town you've warped to.
Now that you a boat, most of the World Map is unlocked. (There is one location you still can't reach until you have a dragon.)
You can - and should! - explore the World Map, and at least grab the available treasure in all the remaining towns. But for the purposes of this walkthrough, I'm going to go through the remaining locations in a specific order, starting with the Mysterious Hut, which is due south of Port City.