Speak with Heron Cogcarrier at the docks in The Commonlands or Sparrow Cogcarrier at -2393, -39, -342 in Antonica and then highlight the small rowboat next to them. You must hail take the rowboat next to the person in the zone where you completed The 999 Year Old Port quest. If you complete this quest in a group and some of you must zone in from another zone, all of you will end up on the same ship.
Speak with Master Chief Gearspanner on the top level of the ship who will ask you to check with the rest of the crew to see if they are ready to get under way.
Note: You can talk with Blendrap the Engineer to learn about the ship and its crew, but it isn't required to complete the quest. Also, if you work on this quest in a group, only one person needs to complete each step in order for all group members to receive credit.
Speak with Bosun Patches. She asks you to kick the sail engine to her right until it is running. You need patience, though, as it will take quite a beating to get it to finally start. Status messages will come up in chat to let you know when to kick faster or slower. You can interact with it by hovering over it with your mouse cursor, and pressing the "f" key. When your chat text shows that the "Wind-O-Matic begins producing an extremely strong wind", you're ready to speak to Patches again.
Speak again to Bosun Patches once you think the engine is running.
Speak with Smith the Cook. He will ask you to balance the weight of the ship by moving five crates of different sizes to one side of the ship or the other. Move the single largest and single smallest crates to one side of the ship and all other crates to the opposite side of the ship. You'll know you've moved the crates far enough because they simply won't highlight any longer.
Read the captain's log, which tells you he plotted a course based on three constellations.
Read the star chart (the astronomy book) and learn about the constellations the captain's log references.
Use the stargazer gadget while facing each of the 4 cardinal directions (north, south, east, and west) and each of the principal directions (northwest, southeast, northeast, and southwest) to determine where the constallations are located.
Head up to the Navitron and enter the direction of the three constellations in order. The correct directions in the correct order are essential, if you get one right and then get the next one wrong, you have to start all over again. The order is random.