Here's a nice little timeline of the evolution of mapping:
Evidence of mapmaking suggests that the map evolved independently in many separate parts of earth. Marshall Islanders made stick charts for navigation. Pre-Columbian maps in Mexico used footprints to represent roads. Early Eskimos carved ivory coastal maps. Incas built relief maps of stone and clay. Chinese literature contains references to maps as early as 7th century B.C.