How did the Europeans communicate with Native Americans?

In most cases, the process went from signs and hand gestures to the acquisition of rudimentary words/phrases to the training of specialized translators.

As for sources, many Spanish accounts including that of Colombus mention using signs to communicate. The sources are more silent when it comes to documenting the extant of bilingualism and the process by which some indigenous people learned Spanish and some Europeans (I say this because in the 1490s there were a lot of Italians and Portuguese members on 'Spanish' expeditions) learned native languages.

Often the process became quicker for subsequent groups because native peoples either were bilingual or had their own bilingual translators for neighboring groups. For example, in many parts of Mesoamerican long distance traders had significant polylingual abilities and even served as embassadors of sorts.

A great example comes from the Conquest of Mexico. After leaving Cuba, Cortés stopped for supplies at Cozumel. The inhabitants spoke Yucatec Maya, the Spaniards did not. But in this case the Spanish were lucky, two shipwrecked Spaniards had found themselves on the island, Geronimo de Aguilar and Gonzalo Guerrero. Both had learned Maya. Cortés offered to have them join the expedition. Aguilar agreed, Guerrero declined as he had integrated himself into the local society (he would eventually fight against other Spaniards when they invaded Central America).

Aguilar allowed Cortés to communicate with Yucatec Maya communities. While traveling along that coast, the party was given a gift of slaves (likely as a gift for them to move on). That gift included a woman who would become known as doña Marina. She was a native of central Mexico and a speaker of Nahautl, the lingua franca of the Aztec Empire. She also spoke Yucatec Maya. From this point Cortés could now speak to pretty much anyone in the region since Maya languages were reasonably mutually intelligible and Nahuatl was the common language for the Aztec Empire and known by many of it's neighbors (there were dozens of not scores of other languages within the empire but Nahuatl allowed communication throughout). Initial translations worked like this: Nahuatl to Yucatec Maya to Spanish and then the reverse.

Eventually, doña Marina learned enough Spanish to cut Aguilar out of the process. It appears that this happened pretty quickly because Aztec accounts really only mention doña Marina who they called Malintzin. (Nahautl does not have 'r' so Marina became Malina and -tzin was added as an honorific, Malintzin basically means Honorable Marina). The Spaniards heard Malintzin as Malinche (there is a very long history of her perception which is a separate story).

Similar processes occurred everywhere else. They key is that basic language acquisition occurred very rapidly (think of how fast an immersion program can build language skills). Once Spaniards or other Europeans had one language they could use that to acquire translators for neighboring languages. Several parts of the Americas had lingua francas, Nahuatl and Quechua being the two biggest, or had several mutually intelligible languages.

Now perfect fluency came more slowly. In the Spanish case, within 20 years missionaries had done a huge amount of work gaining near native fluency and by that point many Spaniards or mestizos and even mulatos and Aficans had near native fluency because of having been raised in homes with native language speakers or having significant social, economic, or cultural ties to native society.

References

Restall, Seven Myths of the Spanish Conquest has a whole chapter on "(mis)communication."

Townsend, Malintzin's Choices gives a great look at her story and the social, cultural context she operated within.