I am not an expert, but I believe that the basic idea was that if you knew the exact time of day then with the position of the sun and stars, you can then infer longitude. The problem of latitude is much simpler, as you can use the highest altitude of the sun in the sky.
For example, take the sun's transit (highest elevation) in Champaign
http://www.wolframalpha.com/input/?i=sun+transit+Champaign
and sun's transit in Peoria
http://www.wolframalpha.com/input/?i=sun+transit+Peoria
which today is 12:02pm versus 12:08pm They are in the same timezone, the difference comes from the difference in longitude.
All you would need was a good watch to know which city you were in. The problem for the early navigators was that they did not have a good watch.
See the article in Wikipedia on the longitude prize
The basic idea was that if you could see the Galilean moons (which is the only connection to Galileo that I know of) and you had a table for predicting their positions, you could infer what time it was. An elegant idea but too elegant. Turned out that they did not obey the simplest model for orbital dynamics, and seemed unpredictable.
While the prize's intention was to have an astronomical solution, I believe the winner was the one who made a good clock.
Later the reason for their unpredictability was given the name orbital resonance. I think rather it is a good example of unpredictability in nature (see Wolfram's A New Kind of Science ) and the only decent predictions come from large computer calculations that simulate their motions.
Of course nowadays you can get the arrangement of Galilean moons on Wolfram Alpha
http://www.wolframalpha.com/input/?i=Galilean+moons+configuration