Longitude is determined by comparing the local time with time at some other location with known coordinates. For example, the easiest place to compare to is Greenwich, England which has a longitude 0 deg 0 min 0 sec. Of course this is only possible with (a) a direct (phone, radio) link to the other location or b) a clock that can keep accurate time while it travels with you.
Before about the year 1763, there were no clocks that could keep accurate time on board a ship, and of course there were no phones or radios. Before clocks, sailors used the following methods:
1. Dead Reckoning
They kept track of how long they traveled at a given speed in a given direction, and marked these on a chart. Click the play button on the interactive graphic below for a demonstration.
Interactive Graphic 8-2-1
This works well for small distances, but little errors add up over time. On a long trip the errors can get quite large. Some say "dead reckoning" is named as it is because one mistake and you're dead.
2. Sailing Down the Latitude
This is where you get on one latitude, the latitude where your destination lies and stay on it, until you reach the destination.
Hazards with this method are:
(a) obstacles might be along the correct latitude path, such as an island, which sailors had to divert around.
(b) they might arrive in the middle of the night
(c) they might miss the latitude by a little and end up missing the island altogether.
3. Celestial Clock
The third method involves using a celestial event whose time of occurrence at the home base can be calculated in advance. Columbus, for instance, used an eclipse to impress the natives but didn't succeed in using it to get his correct longitude.
The moon moves about 1/2° (1 moon diameter) against the background stars, per hour, so lunar occultation (where it blocks a star) is a good time marker. However, the moon's motion is also quite difficult to predict accurately, so this method was much more useful for establishing where one had been (for drawing maps after getting back home) than for determining where one was at a given time.