When two peoples with different languages need to interact over a long period of time, through trade or otherwise, often a pidgin language develops (http://grammar.about.com/od/pq/g/pidginterm.htm). A pidgin language is a language which has no native speakers and is often a simpler version and a mixture of the two languages. If the generation following the generation of pidgin speakers adopts the pidgin language as their native language, it can become a creole language (http://www.britannica.com/EBchecked/topic/142562/creole-languages). The development of pidgin languages and evolution to creole languages is one of the main processes of how language evolves over time. Some examples of existing pidgin are listed here http://aboutworldlanguages.com/pidgin-languages. Perhaps a better topic for /r/AskAnthropology though!

During the Spanish conquest of Mexico, Hernán Cortés came in contact with a fellow Spaniard, Gerónimo de Aguilar, who had been shipwrecked off the coast of Mexico and held captive by the Maya for eight years. He was able to learn the Mayan language through immersion and became a translator for Cortez, along with Cortez's Aztec mistress, La Malinche, who could speak Mayan and the Aztec language, Nahuatl. Basically, La Malinche would speak to the Aztecs and translate what they were saying into Mayan for de Aguilar, who would then translate it from Mayan to Spanish for Cortez.

This section of the FAQ might be of interest: "How did people speaking different languages communicate?"

I think there was a lot of variation in the way this kind of thing worked out. The wording of the question, "when two populations that don't share a language meet..." suggest sustained contact after the first contact. Like two peoples who suddenly live near each other and need to communicate. I think most (known) first contacts were not like this—they were often a relatively short visit by an exploring, trading, or lost ship, or an overland party exploring, trading, or lost. In other words a small group of people who were not sticking around for long.

The way communication occurred, or didn't occur, depended hugely on the context of the contact. Ships seeking to raid islands for slaves would obviously take a very different approach than, say, James Cook. Even for Cook and his crew, who became fairly experienced in "first contacts", results varied wildly. In Botany Bay, Australia, the indigenous people threw stones at Cook's ship, apparently trying to drive it away.1 At Nootka Sound, Vancouver Island, the indigenous people apparently showed no surprise and came to the ship in canoes with goods to trade.2 That second linked book gets into questions about how much we can trust European accounts of first contacts. Rarely were European accounts disinterested. Often they were told and retold to fit various narratives or agendas.

All that said, true first contacts, where there was no way to communicate with words, typically involved a lot of gesturing and sign language. In some cases indigenous peoples had "sign languages" already, for communicating when lacking shared language.3 Sometimes indigenous peoples had large trading networks in which "trade pidgins" developed. This was the case on the Pacific Northwest coast, where Chinook Jargon, or some kind of "proto-Chinook Jargon" existed before Europeans happened by. And then there were cases where learning a bit of one language would be useful in first contacts with other people who spoke related languages. When James Cook "discovered" Hawaii he had a Tahitian sailor with him, whose polynesian language was similar enough to facilitate communication.

When Alessandro Malaspina arrived in Va'vau, Tonga, he had a list of Tonganese words, translated into French, copied from a vocubulary Cook had compiled. But it was a short list and did not work well, perhaps because of differences between English and French. Or perhaps because of miscommunication during Cook's attempt to make a list of Tongan words. Va'vau had been very briefly visited by at least a couple other European explorers, but none stayed long enough to care about communication. Malaspina intended to stay longer. At first, even with the list of words, communication proved very difficult. One of Malaspina's officers, Ciriaco Ceballos, was able to pick up Tonganese fairly quickly, at least enough to allow basic communication. This allowed enough understanding for the Tongans to give Malaspina permission to take on fresh water, set up an observatory, repair their ships, and so on.

(source for that last bit: Alejandro Malaspina: Portrait of a Visionary; John Kendrick; McGill-Queen's University Press, 1999.)

In short, true first contacts, without any clue about language, were probably fairly rare. And even then it was not uncommon for people to have pre-existing methods for dealing with such things—trade pidgins and developed sign language skills, for example.

I feel like there is some answer yet to be had in any of these frequent discussions about first-contact communication. The answers we tend to get are:

1. Fortuitous translators
2. Children immersed for a short period
3. Hand gestures

But what I can't understand is how an explorer is able to have relatively complex conversations in a very short amount of time. Consider, for example, the letter of Columbus from his first voyage.

Columbus arrived in October, and left for his return trip on January 15. Over those couple of months, he visited a variety of places. He traveled up the north coast of Hispaniola, about the half the Cuban north coast, and then to the Bahamas. Thus, he spent a good deal of those months sailing.

So he only stayed with any particular native group for a matter of days. At most a couple of weeks. And yet he had pretty involved communications with them. He reports about things natives told him. He even understood internal politics to certain extent and was aware of the rivalry between the Carib and the Taino. In his letter, he talks about physical descriptions given by the Taino of the Carib, who also describe them as monsters, and the fact that the Carib own numerous canoes and raid from island to island.

Columbus also discusses a local story, which he feels is a myth, about a tribe of warrior women on an island to east. The Taino say the island is rich in copper, which the warrior women use to forge weapons and armor. The The Taino also tell Columbus about an island rich in gold with bald headed inhabitants who are born with a tail.

How in the world can this happen in a couple of weeks? What am I missing?

To add to the question could the use of hostages been encouraged for the reason of increasing communication.

/r/linguistics might be able to help you with this as well.

In European exploration of the South Pacific, one obviously problematic method was to take on a "walking dictionary" (it went by cruder names also). Basically, an indigenous sex slave/concubine/wife, who would gradually learn - and teach - a new language.