For example, the conquest of the Aztecs contains stories of Europeans making treaties, demanding tributes and allying with some native factions. The Spanish and the Aztecs spoke completely different language with no prior contact. How could communication be established?
Can't speak as to Spain, but the French formed native interpreters by bringing natives back to France with them after first contact. More specifically, Jacques Cartier brought back with him the 2 sons of chief Donnaconna on the return leg of his first trip to Canada, wishing they would learn some french and also as corroborating evidence he had reached a new land. He brought the 2 sons back on his second voyage, but left with Donnaconna himself and a few others after that; these never came back to Canada.
Sources:
The history of New France, by Marc Lescarbot
Voyage de Jacques Cartier au Canada, by Jacques Cartier
La ville de Québec sous le régime français, by Pierre-Georges Roy