Mostly this comes down to paying attention.

The first thing is to recontextualize the problem. Imagine a sort of "worst case" scenario, trying to find your way across the vast Pacific Ocean to find a small atoll. An atoll might be only a few km wide at most, and its highest point might be so low that it's basically only visible when you are right up on top of it maybe 5 km or so away. If you imagine trying to sail a straight line across the vast, featureless ocean and arriving precisely within a tiny zone after traveling for many days this seems like an impossible problem.

Fortunately, this is not the only way to solve this navigation problem, there are other ways, so let's go through piece by piece.

Start with sighting land. Being able to see land at your destination directly is one way to know you've arrived but is it the only way? If, for example, the land itself was invisible, are there ways that you could still figure out that it was there or that you were near it? And it turns out there are, if you're paying attention. The presence of birds has always been a big clue of the nearby presence of land which has been used by mariners for ages. Changes in the ocean are also readily apparent. Islands may poke out only a little at the surface of the water, but they are the tips of giant underwater mountain ranges, and beneath the surface they affect ocean currents. The water ocean itself is different around an island, and this can clue you in to the presence of land that you might not be able to see. The very temperature of the ocean can be different as well, since sunlight can heat shallow water around the beaches of an island which then gets carried away as a shallow surface layer by ocean currents. Islands also change the air above them, affecting the weather. Mountains typically create unique cloud formations due to orographic lift of air that passes over them, and these can be visible for much farther away than the mountain itself. Even low lying islands can impact cloud structure due to affecting wind patterns or from the presence of vegetation. And then there is the smell, if the wind is right you can sometimes smell an island from much farther away than you can see it. You add these things together and the result is that you can spot an island from several 10s of kilometers away instead of being able to see it directly on the horizon. This then changes the problem from "make a pinpoint accurate long-distance trek to directly land at the target" to a two part process: first travel to the near vicinity of the island then find the island once you are closer to it. The ocean currents around an island, for example, can give you a direction towards the island (as can birds and the presence of clouds). Even if it takes you a couple tries, looking for an island within a comparatively smaller area of a region a few 10s of km across is much easier than looking for one amidst the expanse of the entire ocean.

But it gets easier than this. Islands in the Pacific are not as a rule just isolated pin-pricks scattered across the ocean, generally they are in chains of islands in close proximity. When you factor in the previous island finding techniques the result is that for long distance travel it's not so much a matter of having to travel to one specific island but rather it's a matter of traveling to a "block" of islands for which all of the "island presence indicators" merge together into a vast feature that is hundreds of kilometers across and tens of kilometers "thick". This dramatically changes the calculus of long distance travel because instead of aiming for a single tiny island you travel in a direction toward an entire giant wall of island indications within the block of islands, and once you reach that then you transition toward more fine grained navigation. You figure out where you are within the island chain and you navigate to the island or islands you want to go to within it. The Polynesians had "stick charts" made of woven, intersecting strips of wood that could record the details of the waves and currents around an island or a set of islands in order to make it easier to navigate.

Of course, these tools and techniques would work hand in hand with working memory as well with people who have made these voyages before. If you have previously traveled to an island chain then going back to it you might recognize where you are and then have an idea of how to get to where you want to go. Most of the time most trips the Polynesians made, even over great distances, were not adventures of exploration and initial discovery, they were regular trade trips with mariners onboard who had made the trip before.

This still leaves a big problem of navigating across large expanses of the ocean in the middle of a voyage however. I'll only cover one detail here which is celestial navigation. If you spend every day on the ocean the starry sky becomes your nightly companion, and you begin to notice lots of details about it. You memorize what it looks like and how it moves through the night (and through the seasons). You start to realize that there are noticeable changes in the sky as you move around. You may not understand latitude but you do understand that the constellation of the Southern Cross sits a different height in the sky depending on how far North you are. These and other similar changes make it possible to determine your direction and your location. If you pay enough attention you can fine tune this knowledge enough to figure out your location to the equivalent of determining your latitude to within a few degrees (a single degree of latitude is 60 nautical miles). This facilitates the process of breaking a journey down into steps and making it possible to figure out how close you are to your destination. You might have a phase of the journey where you are mostly navigating across the open ocean, using the stars to keep you on track and to determine how far along you are at any given moment. When you are closer to your destination you transition to looking for signs of being near land, changes in ocean currents and temperature, characteristic clouds, birds, etc. When you are within a block of islands you navigate towards an island and use your knowledge of that specific chain (via memory, stick maps, etc.) to navigate within it to your final destination.

Make no mistake, these are still tremendously difficult journeys. Even today with modern equipment and sailing vessels these trips are challenging. In Hawaii it's a lot easier than you'd think to screw up and end up on your way to Japan even if you only intended to make a hop between the islands. But these weren't near-suicidal death defying ventures. They required no shortage of bravery to undertake but more than that they required skill and attention. Being tuned in to the subtle clues the environment provides about where you are, where you're headed, and what's nearby. Breaking down the problem into easier to solve sub-problems and working intelligently to solve each. As well as building up and honing these skillsets over centuries of practice.

Some books to read for more details:

• Vaka Moana by K. R. Howe
• We, the Navigators: The Ancient Art of Landfinding in the Pacific by David Lewis