The stars work only if you already know what's out there. The Vikings, if they did make to North America, apparently only made it to Newfoundland. The trip to/from Newfoundland can be made never being more than a few hundred miles from land, which means that birds and clouds and maybe other stuff could be useful as a guide. And North America is a target that's hard to miss. The same is true for Europe on a return journey. None of this is true for Pacific Ocean exploration.
ML/NJ
Another thing I have read that they used is reading the ocean waves. When waves strike an island, they can be deflected or reflected. So when you have a steady wind, and a small swell running counter to the main swell, it will indicate the presence of land.