I'd also be interested in knowing how oral history plays a role in the creation of these maps. Thanks!
(1/2)
This is a really, really big question. I'll try and tackle it, but I want to preface my answer by saying that I'm using a few details to exemplify certain characteristics, trends, or groups of knowledge. I believe a true and anywhere near comprehensive answer would require dozens of books on the subject.
Short answer:
Indigenous mapmaking is an incredibly difficult process, for many of the exact reasons you point out. However, indigenous sources, European accounts, and archaeology are able to provide some information, and combining these aspects can sometimes create generally accurate maps. There is no single best location of this information. In the end, the answer to your question is "cross-referencing every piece of data we have and knowing it's still not enough." I end with recommending Pekka Hamalainen's The Comanche Empire.
(Very) Long answer:
Maps of the Americas have indeed historically deemphasized Native polities. Take, for example, Wikipedia's map of the Spanish Empire "during the second half of the 18th century." The map takes Spanish claims at face value, and often has little relevance to the actual political powers of many locations (the Spanish didn't control the Midwestern U.S. or Patagonia).
So let's talk about how we know the things we do know. I'll mention four major categories (there are certainly more), in no particular order.
Let's start with indigenous histories. Many native peoples of the Americas have geographically informative historical records that stretch back through (and beyond) the colonial period. One of the most impressive of these comes from the Klamath Tribe of Oregon, whose oral history seems to accurately preserve a memory of Mount Mazama's eruption and subsequent evolution into modern-day Crater Lake. This event happened an incredible nine thousand years ago; the eruption has been dated to ~6,850 BCE.^(1) The accuracy of this oral history, and its geologic/archaeological verifiability, tells us that the ancestors of the Klamath inhabited the area around Mount Mazama/Crater Lake around 9,000 years ago.
Of course, few events in human history have been as dramatic as Mount Mazama's eruption, and even fewer survive the millennia as recognizable stories. But, like almost all history, indigenous narratives become more common and more verifiable as we approach the present day. For example, the Mexica (who would eventually be the centerpiece of the Aztec Empire) recognized that they were relatively recent migrants to the Valley of Mexico, and had initially come from a northern land different from the one they eventually built their empire in.^(2) This mytho-historical narrative seems to be relatively accurate, and accords with archaeological findings. The narrative gives hints about the locations of non-Mexica people as well, such as the city-state of Azcapotzalco.^(3) Moving over to the Andes, ethnohistorical sources like oral histories can tell us about things such as Inca forced-migrations of populations (mitmaqkuna), often to the specificity of individual towns and ethnic groups.^(4) Of course, it is important to note that many (but not all) of these indigenous histories are recorded through the lens of colonial European governments, religious institutions, and legal efforts.
It's also common to find European descriptions of unknown or unrecognized peoples in certain locations, and those descriptions can sometimes give historians enough to hazard a guess at which native groups they were talking about. That might take the form of something like "By the big bend in the southern part of x river, we encountered natives wearing y clothes and speaking the same language as our translator z."
Colonizers' efforts to understand the people within "their" borders (again, often for unsavory reasons) is even clearer in colonial and imperialist maps. Many imperial and colonial governments spent considerable resources funding cartography within the borders they claimed. Take a look at this map from the 1804-1806 Lewis and Clark expedition; it's extremely detailed and accurate for the time. Or look at this 1624 map of the Chesapeake Bay, which shows the locations of specific confederacies, tribes, and even tribal villages. Documents like this are incredibly valuable to historians. Interestingly, you can see that the early Chesapeake map very much does not support the later stereotype of Northeastern U.S. Native Americans as completely nomadic people; towns are often marked with drawings of permanent buildings, and the entire top left corner is dedicated to a depiction of Wahunsenacawh (Chief Powhatan) holding court in a large building. Even when colonial maps are incorrect about the livelihoods of the people they were mapping, or their locations, they can have tidbits of useful truth or be incorrect in telling ways. And of course, nomadic groups got written into some maps as well, like this 1854 map of Nebraska and Kansas.
Finally, let's take a quick look at my own specialty: archaeology! In my opinion, true archaeological evidence of a specific community is the "holy grail" of efforts to try and pinpoint where and how indigenous people lived. It can look a little bit past the problems of bias both in colonial and indigenous narratives (although archaeological work is of course always stuck with its own, modern biases) and give us empirical evidence about who was living where at what time. For example, artistic traditions and structural remains tell us about historical polities like the Brazilian Marajoara culture and where they lived.^(6, 7) Even though we have no idea what the Marajoarans called themselves, and lack any indigenous or European knowledge of their civilization (as far as I know), we can say a little bit about the somewhat culturally cohesive group that once lived there. That helps with maps. Other artifacts, like beads and foodstuffs, can give us hints about more nomadic groups that didn't leave as clearly permanent of an archaeological record.
