I have wondered this a few times while reading.
How was Cortés able to gain support from Aztec rivals? Surely they would need to communicate fairly well to work with him?
In 1607, Powhatan addressed a plea to John Smith. What language did he write it in? Did he know that language or did an aide translate? I saw that plea in A People's History of the United States by Zinn as:
I have seen two generations of my people die.... I know the difference between peace and war better than any man in my country. I am now grown old, and must die soon; my authority must descend to my brothers, Opitehapan, Opechancanough and Catatough-then to my two sisters, and then to my two daughters-I wish them to know as much as I do, and that your love to them may be like mine to you. Why will you take by force what you may have quietly by love? Why will you destroy us who supply you with food? What can you get by war? We can hide our provisions and run into the woods; then you will starve for wronging your friends. Why are you jealous of us? We are unarmed, and willing to give you what you ask, if you come in a friendly manner, and not so simple as not to know that it is much better to eat good meat, sleep comfortably, live quietly with my wives and children, laugh and be merry with the English, and trade for their copper and hatchets, than to run away from them, and to lie cold in the woods, feed on acorns, roots and such trash, and be so hunted that I can neither eat nor sleep. In these wars, my men must sit up watching, and if a twig break, they all cry out "Here comes Captain Smith!" So I must end my miserable life. Take away your guns and swords, the cause of all our jealousy, or you may all die in the same manner.
It always struck me as a well-written statement in which there was no trouble with the language. Was the original statement that well-written? Or is that a feature of it having been retranslated by history and smoothed out?
There's always room for discussion, but perhaps the section Cross-cultural communication and lingua francas from our FAQ will answer your inquiry.
Gerónimo de Aguilar was enslaved by Mayans after surviving a shipwreck, and learned to speak Yucatec while living with them for several years. Subsequently Cortés met up with him and he acted as the conquistadors' translator between Yucatec and Spanish.
Shortly thereafter Cortés was given a slave who spoke both Yucatec and Nahuatl, who was baptized as Marina. Nahuatl was widely used as a lingua franca by many different indigenous groups, so the Spaniards could communicate by having Aguilar translate from Spanish to Yucatec and then having Marina translate from Yucatec to Nahuatl (and vice versa).
Over time, Marina learned to speak Spanish as well, enabling her to translate between Spanish and Nahuatl directly without needing Aguilar.
They probably had other interpreters too, who are less well-known to history. E.g. the Codex Chimalpahin mentions a translator named Tomás in addition to Marina.