Latitude can be determined quite accurately by sighting the sun or stars. Longitude, on the other hand, requires accurate timekeeping which, as you note, wasn't readily available at sea prior to the Harrison chronometer. All navigators had was their best guess.

As a result, ships were quite regularly far to the east or west of where they thought they were - by hundreds of miles - though it was much harder for them to be off to the north or south. Look for a book called "Lost Islands" by Henry Stommel. It's about islands that were previously accepted as real and added to maps and navigational charts, but which don't really exist.

A few of these were simple fraud by captains who had some motive to lie about having discovered an island, but a huge number of them were real islands that had already been discovered and correctly noted on charts, well to the east or west of where the phantom new islands were supposed to be.

It depends a bit on what you're talking about. A lot of water transport was, and is, in more or less coastal waters, in those cases you could navigate by landmarks on the shore, or even the type of dirt on the sea bed (a small sample could be brought up with the lead when plumbing the depth)

For crossing an ocean that would't do, as /u/Naberius points out latitude was relatively easy to figure out as long as you kept your eyes on the sun and stars. Longitude was more of a challenge. One way i know European mariners used was to keep track of the speed of their ship, by paying out a line with knots in it, tied to a board. Trouble is, this gives you your speed through the water, not over the ground. If there's a strong current the difference can be huge.

The Polynesians apparently used wave patterns to navigate between their islands and had maps made of sticks to document them, but unfortunately i know no more than that.

PS: If i'm not mistaken the Antikythera mechanism was for making astrological calculations (e.g. figuring out when an eclipse would happen) not navigation.