Well, some societies did leave a written record (Mi'kmaq, Maya, Zapotec) and others had long standing traditions of oral stories that were passed down through the generations that were recorded in writing by others. There's also the archaeological record which helps to piece together bits and pieces of past people to understand who they were, sometimes relying on analogies with better known people who may share some similar traits. There is also descriptions people made when meeting new and diverse groups. Huge works like the Florentine Codex by Sahagun have proved to be greatly insightful as well as the letters Pizarro wrote to the king of Spain.

Hey there! I totally agree with what /u/Mictlantecuhtli has written thus far, but thought I would flesh out the response a little bit.

Lots of Indigenous societies did leave material traces of their histories, though since they are not alphabetical, it is harder for outsiders to "read" them. For example, in 2009, a group of Haida worked with staff at the Pitt Rivers Museum to expand the knowledge about the Haida objects in the museum collection. There is a 50 minute documentary about the process, called Everything Was Carved that you can watch online. It clearly shows how Haida were able to tell the museum "experts" things about the use of material culture which can contribute to our knowledge of pre- and early-contact Haida societies.

Oral tradition is also a really important source for historical knowledge about Indigenous peoples, as is archaeological analysis. I already talked about those things in another comment on this subreddit so if you're interested you could check that out too.