Interpreters and isolated populations

This is something that’s been bugging me for a while - and try as I might I couldn’t come up with a snappy title to convey what I mean.

In the age of European exploration, obviously the explorers encountered loads of native people who had never had any contact with Europeans, and spoke languages that (presumably?) were unrelated to European ones. And yet in almost every case, the explorers - or certainly missionaries who came later - managed to communicate with these people, and learn the local language.

How did they do this? If you have no common ground whatsoever, how do you figure out what words mean what? Sorry if this has been asked before - I’m on a very slow connection and searching is just too horrible a proposition.

In sign language this is one of the first interactive exercises the students perform. Two students are put in a room and told they are unable to talk but must establish a basic mode of communication, and maybe solve some kind of minor conflict. Invariable this leads to a lot of miming and facial expressions. The goal is to teach the value of facial expression and get the student to understand that the somatic components of communication are almost as important as the verbal ones.

In short, body language.

It may take some time to learn a totally foreign language, but if you have to, you´ll pick up the basic concepts pretty quickly. Body and sign language, as pointed out by Attrayant, play an important role in this, and pointing at objects to find out their name.
You won´t be able to discuss theology with the people, but that´s not really what the first explorers/conquistadores were interested in. And things like “where´s water?” “where do you get all that gold?” and “take me to your leader” can be communicated pretty easily, especially at swordpoint.
Then later, if they were interested in actually communicating with the people and not just killing/robbing/taking them as slaves, they used their own or native interpreters, people who had a talent for learning foreign languages. If you live among people who speak another language, you´ll learn it sooner or later. This was, e.g., the case with missionaries. In many cases, linguists/ethnologists went and deliberately studied different peoples and their languages - this was later, though, 18th/19th century, I guess (sorry, no cite). And it was the case the other way round, too - indigenous people who were brought to Europe, often as a curiosity, learned the language and could interpret later.
This is just a dim recollection of what I´ve read, I can´t provide any cites right now.
(A friend of mine wrote her thesis on the role of interpreters in the conquista of South America, very interesting topic!)