The answer is rather intuitive: they would have some indigenous people as interpreters. When the Spanish and the indigenous populations would make first contact, the natives would come towards the Spaniards, and the Spaniards would show them the boats, etc. With very much care, by signs, the Spanish people would try to communicate to the indigenous that they wanted to have one or two of the indians with them as interpreters (lenguas, in Spanish), and there would be no problems with that. Both groups of people would be very much interested in having the ability to communicate. I'm going to quote my good captain Oviedo about Columbus:
E llevó de este camino el Almirante nueve o diez indios consigo, para que, como testigos de su buena ventura, besasen las manos al Rey e a la Reina, e viesen la tierra de los cristianos e aprendiesen la lengua, para que cuando aquestos acá tornasen, ellos e los cristianos que quedaban encomendados a Goacanagarí, y en el castillo que es dicho de Puerto Real, fuesen lenguas e intérpretes para la conquista e pacificación e conversión destas gentes.
Translation: And by this way took the Admital nine or ten indians with him so that, as witnesses of his good fortune, kissed the hands of the King and Queen of Spain, and saw the lands of the christians, and learnt the language, so that when they came back here, they and the christians that had been given to Goacanagarí to supervise, and in the aforementioned castle of Puerto Real, be languages and interpreters for the conquest, pacification, and conversion of these peoples.
Christopher Columbus himself, on his diary of the first navigation, in a copy by Bartolomé de las Casas, mentions from time to time the need of languages, or the fact that they somehow communicate through the use of signs. On October the 24th he notes this:
Esta noche a media noche levanté las anclas de la isla Isabela del cabo del Isleo, que es de la parte del Norte, adonde yo estaba posado para ir a la isla de Cuba, adonde oí de esta gente que era muy grande y de gran trato y había en ella oro y especierías y naos grandes y mercaderes, y me mostró que al Oessudoeste iría a ella; y yo así lo tengo, porque creo que si es así, como por señas que me hicieron todos los indios de estas islas y aquellos que llevo yo en los navíos, porque por lengua no los entiendo, es la isla de Cipango
Translation: This night at midnight I rose the anchors from cape Isleo in Isabela island, that is on the northern part, where I was stationed in order to go to the isle of Cuba, of which I heard from people that it was very large, and of big business, and there was there gold, and spices, and big ships, and merchants, and showed me that on the Westsouthwest I shall get there. And I think so, for I believe it is so, as by signs that all the indians of these islands made, and the ones I have on my ships, because through language I don't understand them, is the island of Zipango.
Then, there is the odd circumstance when it happens the other way around, namely a Spaniard that is captured by the natives, and eventually learns the language. There are two notorious cases of this: Fray Jerónimo de Aguilar, and Gonzalo Guerrero. These two fellows were captured by the mayans and enslaved, but their fates became very different. Gonzalo Guerrero ended up marrying the daughter of a mayan ruler, serving as commander of his forces, to which he taught the Spanish tactics and techniques, even managing to defeat three Spanish attempts at taking his domains. Aguilar, on the other hand, never became a mayan, always resisted through his faith in Christ, and was eventually rescued. Aguilar was of very much help to Cortés as an interpreter. Malintzin spoke nahuatl and mayan, whileas Aguilar spoke mayan and spanish. So, that way they had and adequate communication channel.
As a side-note, I am going to give an anecdote from Cortés
Este valle e población se llama Caltanmi, e al señor de él, por su nombre proprio llaman Olintecle, como se dijo en el capítulo primero. Allí fueron los españoles muy bien aposentados e servidos. E después que Hernando Cortés hobo hablado a aquel señor muy amorosamente, e le dijo que eran los cristianos, e que iban a aquella tierra por mandado del Emperador universal de todos los cristianos, e le dijo, cuan encarescidamente supo, la grandeza e poder de César, preguntóle, por las lenguas, si era vasallo de Montezuma, o si era de otra parcialidad u opinión; el cual, muy admirado e como espantado de tal pregunta, le respondió e dijo así: "¿Quién no es vasallo de Montezuma?" Queriendo decir que Montezuma era señor del mundo. A lo cual Hernando Cortés le replicó sonriéndose, como quien burlaba de su ignorancia, e le dió a entender que se engañaba, e manifestóle el poder grandísimo del Emperador, diciéndole que había otros muchos en el mundo más poderosos que Montezuma, e ninguno igual del Emperador
Translation: This valley and population is called Caltanmi, and its lord is called Olintecle, as said on the first chapter. The Spanish were very well acommodated and served there. And after Hernando Cortés had talked to that lord very lovingly, and told him that they were christians, going to that land by command of the universal Emperor of all christians, and told him, with as much detail as he could, of the greatness and might of Caesar, he asked, through the interpreters, if he was a vassal of Montezuma, or if he was on a different faction. He answered, bewildered at the question, "Who isn't a vassal of Montezuma"? Like trying to say that Montezuma was lord of the world. To which Hernán Cortés replied smiling, as someone mocking the other's ignorance, and had him understand that he was wrong, and manifested him the enormous might of the Emperor, saying that were many more in the world more powerful than Montezuma, and none as the Emperor.
Sources:
Fernández de Oviedo, Gonzalo (1535), Historia General y Natural de las Indias. Sevilla: Montesdoca. Modern edition by Juan Pérez de Tudela (1959, Madrid: BAE)
Colón, Cristóbal (2007), Los cuatro viajes. Testamento. Edition by Consuelo Varela. Madrid: Alianza.
Amores Carredano, Juan Bosco (2006), Historia de América. Madrid: Ariel.