Many early maps were based on observations made by the great explorers, such as Christopher Columbus and Captain Cook, who were cartographers as well as sailors and navigators. This site explains in a bit more detail how it was done.
http://www.collectionscanada.ca/explorers/h24-230-
e.html
Things
haven't changed much these days either ... we poor surveyors are always being sent to outlandish places where there are no mod cons... like Wolverhampton!! ;) Luckily the technology has improved, though, so it no longer takes 5 years! Incidentally, many large scale surveys are now done using GPS instead of aerial photography.