Once you arrive in Albrook, stock up some items and head south to the harbor. When you enter, head along to find General Leo on the ship. Speak with him and you’ll be “introduced” to some “strangers” – Celes and Shadow.

Celes and Locke kinda freak each other out, with the former fleeing. Anyways, it seems arrangements have been made for you at the Inn, so it’s free for a single night. Go back to the Inn. On the way, before exiting the harbor, be sure to examine the crates near the harbor entrance for a Teleport Stone . Head to the Inn and speak with the manager to sleep in for the night. There will be a scene in the night.

In the morning, head to the harbor and set sail.