The ability to reliably get from one place to another has been fundamental since ancient times. The first known recordings that could be considered maps were actually of the heavens, and not the Earth. Since the earliest civilizations were spread over relatively small geographic areas, the position of the stars would have been essentially fixed no matter where one was at. Earth based landmarks and well travelled paths were the primary travel tools of ancient times, while the stars allowed for navigation beyond what was just above the horizon.
The most basic necessities for navigation are direction and distance. Knowledge of the Earth being round was generally accepted by most early philosophers, and the concept of longitude was well understood. However, without the ability to accurately measure longitudinal distances based on latitude, world wide maps were wildly inaccurate. Tied into that was the problem of representing a curved surface on a flat map.
Numerous civilizations including the Greeks, Romans, Chinese, Indians, and Persians, made maps that covered relatively small areas and were decently accurate. These maps were based on local geographical features such as rivers, mountains, coastlines, and other fixed locations. Once settlements and routes were established, maps were made using those as references as well. Distances were measued based on normal travelling pace be it on foot or animal. Direction was determined by the sun and stars. The curvature issue had minimal impact on small distance measurement and representation, but as the known world grew, more civilizations began trading information, and once open ocean exploration began in earnest, these problems limited the potential accuracy of large scale mapping.
The earliest maps, all the way up until the age of discovery, were primarily regional, though there were various attempts at world wide mapping. The earliest known ones have been credited to Anaximenes, and a derivation by Herodotus, dating from around 500 bc.
The most well known and widely used early maps were the ones made by Ptolemy. In particular his world representation. While no original versions are known to exist, later derivitives referencing his work Geographia, Ptolemy collected and presented a number of regional maps in an atlas form, including a single combined world map. His maps were the first to depict lines of latitude and longitude, thus laying the grounwork for the first world wide coordinate system.
For over a thousand years, his world maps were the standard reference and were constantly refined by explorers and cartographers as new data and measurements became available throughout the centuries. The first true nautical charts providing accurate navigational information began to appear at the end of the 13th century detailing the Mediterrainian Sea. In 1375, Atles catala was made. It featured a grid system, and the first compass rose found on a map.
Ptolemy disregarded Eratosthenes' estimate of the Earth's circumference, instead, assumed a circumference about 40% smaller. Ptolemys world maps, and other attempts at world mapping, did have their limitations though. Most information was gathered from travellers, and land explorers where there was little standardization in measurement and record keeping. They also suffered from the longitude problem. Understandably, lack of actual data was a big issue, especially when trying to record out of sight of land oceanic travel where there were no landmarks, or paths to follow.
Ptolemys' maps were based on a longitude 0 meridian that passed through the western most known land named the Fortunate Isles, or Canary Islands by early seafaring explorers. Since the Canaries were relatively easy to reach as they are not far off the coast, their locations were well known at the time. They are however far enough off the coast for the longitude problem to become a factor. Nautical estimations of the distance at the time, paired with known land based distances, led Ptolemy to underestimate the circumference of the Earth in order to take into account the nautical distances and to force the Fortunate Isles into the location he thought they should be. While the smaller circumference allowed him to place the Canaries where he thought they should be, if one were to project the same maps with the same measurements using Eratosthenes' circumference, Ptolemy's 0 meridian Canary Islands were not actually the Canary islands, but quite possibly the eastern Antilles islands in the New World.
The Age of Exploration saw a renewed necessity for map making and navigational accuracy. While there is a certain romanticism with the Age of Discovery, it was the economic pressures and demands that pushed discovery forward. Huge sums of money were paid, and large expeditions were funded by governments and empires in search of new resources and trade routes. The development of larger, sturdier ships, improvements in navigational tools, and the promise of great riches, gave rise to the great explorers including Vasco da Gama who led the first expedition around Africa to India, Pedro Alvares Cabral who landed in Brazil, Christopher Columbus who established contact with the America's, and of course Ferdinand Magellan and Juan Sebastian Elcano, the first recorded circumnavigation of Earth.
Those great expeditions, along with countless others pressed the need for more detailed and accurate maps. The huge explosion in records from these expeditions led map makers to be able to make far more detailed maps with features of particular interest to maritime explorers including coastlines, rivers, harbours, straights, and ports. These maps included compass lines and roses, new projections to more accurately take into account the Earths curvature, and in 1492, the first globe was made. The first true nautical chart with scales of latitude was the Atlantic Chart of Pedro Reinel in 1504.
As exploration became world wide, the first true world map with most major landmasses generally in the right locations was made by Martin Waldseemuller in 1507 based on Ptolemy's coordinate projection. Finally, in 1569, Gerard Mercator developed a new projection that had a global scale focus with equatorial emphasis. This projection, which is still the primary map projection currently used, produced the first maps readily recognizable as the world we know today.