How does navigation work in One Piece universe?
Navigating is as easy as the goodness of your maps and directional devices. So in general I would suspect navigating to be as difficult for the Strawhats as for any other pirate crew. Pirates usually have the same amount of resources to start with. If anything it should be easier for the Strawhats because Nami has been looking at maps since she was just a child. Although this advantage was never really mentioned in the series and I don't think she was actually able to exploited that knowledge (yet?).

Now you are correct in saying that it is much easier for the Marines to navigate through the world and this makes a lot of sense. The Marines and the World Government have been around for more than 800 years, since the Void Century. Therefore they were able to draw maps of the entire world and would have been able to create many eternal poses for all available islands.

Books with maps are available in local stores or libraries as we can see how Nami's room at Arlong's park was filled with these books. Pirates would be able to obtain these books, but with the WG having much greater funds, I would assume every ship to have such maps available to navigate through the seas. The fact that the Marines travel by map can be seen in chapter 321 when Aokiji takes his map to check the location the Strawhats are about to travel to.



While on the grandline, the Marines use eternal poses to navigate. This can be seen in chapter 128 when Smoker asks for an eternal pose to Alabasta. All they really need to do is contact Headquarters and they will send them an eternal pose, presumably by air similar to the newspaper birds.



With the number of smart scientist the WG would have had over the years, it wouldn't surprise me if the WG would have similar devices for New World. I don't recall there being any mention of such a device just yet though.