If one does not need to care about adverse effects due to the lack of magnetic field around Earth, then the question is essentially "what if there were no magnetic north/south pole" as this will be the major thing which affects navigation. The short answer is that it would be "same, same, but different"
If we disregard the fact that no magnetic field around the Earth means that there would be no humans around, as tj1000 points out, then there would likely not be that much significant changes (as long as the world would work exactly the same as now, but without a magnetic north/south). Humans navigated by stars, landmarks and several other tools long before they discovered the magnetic north and would simply continue to do so without a magnetic compass.
Navigation largely means "at sea"; throughout the history the way to find ones way have been the hardest at sea where there is nothing but water to look at and everything looks the same. Navigating on land can be done entirely by landmarks and the same goes for aerial navigation (since high altitude flying and flying cross large bodies of water is a relatively recent "fad"). This means that the majority of the tools have been used on boats, but several of them were developed for astronomy before they were discovered to be useful for navigation.
Short history of navigation methods
The following information is compiled from the Wikipedia page on the history of navigation.
Following the coast line (since the start of sailing). This has been among the first ways to sail, where few dared to venture so far from land that they no longer could see where they are. In essence, this is the same as navigating by landmarks.
Following celestial bodies (since centuries BCE). By simply setting sail towards a celestial body, or by keeping it constantly on one particular side, will help a sailor to (hopefully) keep a straight path. The problem is, of course, if the celestial body moves fast enough to not be a reliable fixed point. It is known that ancient Greeks used this way of navigating and it is mentioned at one point in the Odyssey that Odysseus should keep Ursa Major on his left side while observing the Pleiades to get across the ocean from an island.
Nautical Charts (From ~500 BCE to present time). The Nautical charts are the maps of the seas, they show coast lines, treacherous regions and sometimes water depths and other useful information. While a map is good to have, it has limitations if one completely loses ones bearing and they are best used with another tool to keep track of position. Without other tools, they still help a sailor to navigate once a charted shore is reached.
Antikythera mechanism (around 100 BCE). The first analog computational device, built by ancient Greeks and then lost in history. It was used to predict the movement of celestial bodies and may have been used for navigation. The device was not incredibly accurate as the theory of the movement of celestial bodies was not sufficiently developed at that time, but the clockwork mechanism itself was a masterpiece.
Measuring depth (Since some centuries BCE). The Phoenicians and the Carthaginians realized that if they measured the depth of the ocean, they could estimate how far they were from land; they did so by lowering a weight on a long rope until it hit the bottom. Experienced sailors among them were even said to be able to tell their location based on the sand they pulled back up. Apparently they got as far as Senegal in Africa by this method.
Magnetic compass (~1000 CE in Asia and ~1200 CE by Europeans and Arabs). The magnetic compass was invented more than 2000 years ago (around 300-200 BCE) in Asia and was then used for fortune telling. It was adapted for navigation much later and quite rapidly got a widespread use as it allowed for easy navigation even when no other ways were possible (cloudy sky, etc.). It reached destinations along the Silk Road, which could be an indication that it was used for land navigation early on. Arab sailors have been famous to use it early on, but there are older documents mentioning it among Europeans than Arabs; whom got it first is disputed, but it's largely around the same time. Drawbacks: The magnetic compass is sensitive to large bodies of iron or other ores which can be magnetized, it is also largely useless near the poles (although few early explorers were near the poles), and it can be treacherous when passing the equator. The compass is drawn to the magnetic north/south pole, which means that when one is in the northern hemisphere, then the north side will be drawn downwards, and vice versa, the southern pin will be drawn downwards when in the southern hemisphere. The compasses are weighted to counter this drag (differently weighted for northern and southern hemisphere) and will work poorly if one crosses the equator as the counterweight will no longer fill it's purpose; there is a risk that the compass gets stuck and no longer shows the magnetic north/south if it's used in the wrong hemisphere. This drawback, however, is often corrected for in modern compasses.
Kamal, Cross-staff, Backstaff, Quadrant, Sextant, Octant, and similar tools. (from late 9th century CE and onwards). All of these tools are iterations on the same principle and the original tool was developed for astronomy (in ancient times) to measure angles between celestial bodies or between one body and a landmark (horizon). The various tools differ slightly of exactly how they can be used, but the basic principle is nearly the same. They are high precision tools and have been essential for navigation between 15th century CE and modern times. With these tools and an accurate time measurement (usually water or sand hourglasses; The British Royal Navy used hourglasses for timing their watches until 1839), it was possible to establish both latitude and longitude of the ship.
Gyrocompass (first patent 1885, first usable one in 1906). A gyroscopic compass relies on the gyroscopic precession to find the true north relative a fast spinning disc and the rotation Earth. It has the advantage to not be reliant on the magnetic north and that it's unaffected by large quantities of ferromagnetic material (such as the hull of a modern boat).
Conclusion on navigation history
While the magnetic compass have been an extremely valuable tool for navigation, history reveals that there has been over a millennium of navigation without the use of a magnetic compass and that there have been an array of tools used during the millennium where the magnetic compass was used. It should, thus, be relatively safe to be navigating the world without it and we would have been able to reach all corners of the planet even if we had no magnetic compass available.
How about the influence of the moon?
I believe that JDługosz's answer is correct: The early compasses would probably have been to weak to pick up the influence of the moon and, thus, never invented. If it were possible to build a device which points to the moon, then it would be highly difficult to navigate with it as fixed point as it travels too fast when the planet spins (unless one can see the moon, then one have no clue if it's aligned with where one wants to go) - it's safer to use the sun or other stars as reference points, and that would likely be the way to do it.
Other implications with a lack of magnetic field
Exactly which changes in science there would be from not developing the compass is impossible to say; there is a risk that electromagnetism would never be discovered, but since magnetism itself would still be around, it's unlikely that there would be more than a delay in it's discovery (magnetism were probably discovered with the discovery of the early compass, but the magnetic properties would have been discovered eventually).
As long as there is not too much changes in science, there would still be advances in navigation, inventions such as the gyrocompass and GPS do not rely on a magnetic north and are inventions just waiting to be discovered. However, in reality, we wouldn't be able to discover electronics without a protective magnetic field around us, so exactly what could be discovered depends on how much reality you want to have in such a world.
Thus, the answer lies somewhere between "there would only be some delays in discoveries, otherwise the world would largely look the same" to "our inventions would never improve past renaissance technology". As for navigation in itself, it would for sure be tricker to navigate in a dense forest without a compass (or GPS...), but seafaring and flying would likely not be much affected. In reality, though, tj1000ng's answer is correct: there would be no navigating humans around.