When you say most natives (Amerindians) were not literate, the same could be said of many Europeans and Colonists for that matter until the early industrial age. This is why Christianity was so popular, the Bible was one of the few books that the masses knew until the Age of Enlightenment. Like most civilizations, literacy and writing were mostly reserved for the elite, or in this case, the elder or priest-caste. For nomadic tribes, stories survived in other forms, through artwork and oral tradition- much like the pagan traditions from ancient nomads of Eurasia and Africa.
Most of the first accounts of the European explorers and colonists were passed down orally or transcribed by the Europeans who interacted them. This link from the National Humanities Center has a brief compilation of accounts from the Mexica, Tlaxcala, Maya, Ho-Chunk, and Micmac. This is by no means the extent of what's been documented, there are many accounts that survive in tribal oral traditions and in the long-lost archives of royal courts, the Vatican, and even old newspapers of the early settlers.
These accounts can be grouped for various perspectives: (1) the "first
encounter" narratives of the Mexica and the Ho-Chunk; (2) the conquest
histories of the Mexica, Tlaxcala, and Maya; (3) the response to
French "superiority" of the Ho-Chunk and the Micmac; (4) the
resistance to the "oppressors" of the Maya and the Micmac. In
addition, you can compare the accounts by their source, from
eyewitness accounts to oral traditions transcribed centuries later,
and by their recorder, from a 16th-century Spanish priest to a
20th-century American anthropologist.
As legend has it, when Moctezuma first heard of the Spanish visitors, he sent messengers and offered gifts, believing they may have been divine entities, but eventually, he realized the folly of his error and knew for certain they were only men. He tried to keep up appearances for his people, but it was too late by then, he was shortly captured and held as a prisoner for ransom.