I can only speak for Canada, but based on early accounts of missionaries and literature by Indigenous authors, it could take a few weeks or months to establish basic communications (for food or survival things, basically survival communications), but missionaries have written that it could take years to master a new Indigenous language as they were moving further to the interior of the lands. Oblates missionaries wrote that except for a few exceptions, it was almost impossible to master perfectly an indigenous language. However, what helped was second-generation communications. Even before the time the Métis were established as a distinct people, they could effectively act as translators between their fathers' and mothers' languages.

There is also ample evidence of some languages that were developed and used as intermediary between European languages and various Indigenous languages after a few centuries (Chinook on the west coast - the trade jargon; Michif - the Métis language). Along with many indigenous languages, they are still spoken today if you are interested.

It also depends on the circumstances of the meeting. This can be due to Indigenous internal foreign policy, what they heard about foreigners via their informants, how the explorers behaved in different regions when they arrived, etc. Some people (like the Kwakwakaw'waks) were less willing to work with early anthropologists, or less welcoming of missionaries, so in case of early tensions it takes longer to learn the language as opposed to favorable circumstances where trade is established for instance. Obviously it also depends on the linguistic abilities of the explorers and indigenous people they met with.

sources: Oblates missions, O. Dickason, G. Sioui, Macdougall, T. King.

edit: added sources and some precisions.

There has been quite some discussion on this topic already, e.g. in the faq section „How did colonialists talk with natives“. Generally for the early stages of contact the importance of interpreters and translation is highlighted, as well as the use of pidgin languages during prolonged contact (eg. but not only for trade, as discussed in other posts above).

As there has already been quite some discussion on Canada I'll be looking at Spanish America, and more specifically early colonial Mexico (New Spain), where esp. during the campagins of the Spanish „conquest“ interpreters played a major role. This is from an earlier answer of mine (dealing more with how contracts were made at the time) looking at Cortés' interpreters:

[...] after initial contact interpreters and translators played increasingly important roles. The example of Cortés' campaigns in Mexico shows this, as translators like the Spaniard Géronimo de Aguilar and the Nahua noblewoman Malinche (to the Spanish « Marina ») made communication and thus alliances with various native population groups possible. Restall has a good discqussion of the rôle of interpreters in the conquests in his « Seven Myths of the Spanish Conquest » (ch. 5). He mentions that Aguilar who had been stranded in Yucatan spoke Mayan and Malinche knew Mayan and (the main Aztec language) Nahuatl but little or no Spanish – so that Cortés communicated with Nahuatl speaking lords through the triangle of his two interpreters [just to add here that Malinche later learned Spanish, simlifying the process]. This system was clearly imperfect but still allowed for basic communication. Thus Restall challenges myths of both the Spaniards' 'superior' communication skills, and of suppesed extreme miscommunication taking place. Interpreters played silmilarly important roles in Pizarro's campagins in Peru, as well as in other Spanish American regions.

We can see here the clearly exceptional position of a few interpreters during initial contact. Looking forward to the first decades in colonial Mexico, we can see how the „language barriers“ were starting to be bridged more frequently, but still in special cases mostly related to Europeans from the religious orders, and to a small educated native elite. The Franciscans played an important role in educating native people in Spanish, Latin; theology and other humanist subjects, above all in the Colegio de Santa Cruz Tlatelolco founded by the Franciscans in 1536. Very briefly put, its main goal was at first to educate indigenous priests in order to further conversion – a conversion process to Christianity that was increasingly seen an „not very successful“ in large part due to the difficulties of communicating Christian teachings to native people who for the most part reaminedy slow/reluctant, understandably, to pick up Spanish.

In this light, we have to see someone like the native noble Antonio Valeriano as still an exceptional case – he worked and taught in the Colegio de Santa Cruz, and was fluent in Latin and Spanish for which he was often praised by the friars. He also collaborated on th Franciscan Bernardino de Sahagún 's huge „Historia General“ , which was first written in the then main native language Nahuatl: Showing on the other hand Sahagún's familiarity with the native language. With these short examples I've tried to show that at a rather early stage of colonial life (mid to late 16th c.) there were already both native and European scholars (those mentioned being only two well-known examples) more or less fluent in the respective other language(s) – with the first post-conquest generation. But also that we're still looking at a quite small minority of people who had an exceptional interest in learning and teaching these languages, also via early grammars, and esp. A religious and political interest connected to Christianization; but also leading to early possibilities for native elites to „climb the social ladder“. That is not to say that translations had only religious functions, as they played a major role in many other areas including administration, esp. in the process of how Spanish/colonial authorities distributed traditional land titles and other privileges to Spaniards and indigenous people.

I don't want to stray too far from your question here, so I'll just add a few more points that seem relevant: First , in New Spain we see later on a first generation of actual bilingual scholars at the turn of the 16th c. coming up – people born after the „conquest“ period. This included both indigenous and mestizo writers writing chronicles in Spanish and Nahuatl (e.g. Hernando Tezozómoc, Domingo Chimalpahin), and Spanish friars consulting native codices and Nahuatl writings (like the Franciscan Juan de Torquemada).

Second, important lignuistic work was done in this context by James Lockhart (see his „The Nahuas After the Conquest), who highlights different developmental stages in (not only) the development of Nahuatl drawing on sources from many different social contexts. Again briefly put, he describes the early stage of initial contact with both Spanish and Nahuatl remaining relatively apart; followed by the second stage from iirc the late 16 to the mid 17th c. with stronger miscenation between the languages involving loan words and borrowings; and a third stage after with even stronger and more common incorporation of Spanish words and grammar into Nahuatl [I remember him adding a 4th stage, and am probably leaving out important details here I'd have to get back to]. This is to say that the „corroding“ of language barriers in colonial Mexico did not only pertain to elites, but increasingly influenced commoners and other groups (in Lockhart's studies native groups) as well.

And third, just to add again that on a more general level the level and consistency of language exchange and possibility for early translations often depended on how strong contact between two groups of speakers were – as close as in the Mexican example here („close“ in a forced way, as in due to colonisation), or looser contact ie. with trade that might lead to the initial development of pidgins.

Edit: Added 2 sentences for context.

In some cases natives were kidnapped, brought to Europe, learned the language, and in rare cases, eventually made their way back home...

In particular, the story of Tisquantum ("Squanto" as he is more well known today) is interesting.

"Mourt's Relation: A Journal of the Pilgrims at Plymouth" recounts:

"Thursday, the 22nd of March, was a very fair warm day. About noon we met again about our public business, but we had scarce been an hour together, but Samoset came again, and Tisquantum, the only native of Patuxet, where we now inhabit, who was one of the twenty captives that by Hunt were carried away, and had been in England, and dwelt in Cornhill with Master John Slanie, a merchant, and could speak a little English, with three others, and they brought with them some few skins to truck, and some red herrings newly taken and dried, but not salted, and signified unto us, that their great sagamore Massasoit was hard by, with Quadequina his brother, and all their men. They could not well express in English what they would, but after an hour the king came to the top of a hill over against us, and had in his train sixty men, that we could well behold them and they us. We were not willing to send our governor to them, and they unwilling to come to us, so Tisquantum went again unto him, who brought word that we should send one to parley with him, which we did, which was Edward Winslow, to know his mind, and to signify the mind and will of our governor, which was to have trading and peace with him. We sent to the king a pair of knives, and a copper chain with a jewel at it. To Quadequina we sent likewise a knife and a jewel to hang in his ear, and withal a pot of strong water, a good quantity of biscuit, and some butter, which were all willingly accepted."

The question is: How did Tisquantum know any English at all?

Tisquantum/Squanto was captured by George Weymouth around 1605, spent 10 years in England, returned with John Smith in 1615, was subsequently tricked into slavery with 24 others by Thomas Hunt who tried to sell him in Malaga Spain... but was saved by Spanish Friars who wanted to teach them Christianity. Eventually, Tisquantum made it back to England and lived with John Slaney. Tisquantum returned to his homeland from England for a second time in 1619... just in time to make it into every school's Thanksgiving play from then forward.

Sources: Kinnicut "Plymouth settlement and Tisquantum"

Here on the Eastern Shore of Virginia there is a well documented case of an exchange of young people between the indigenous people and the English colonists expressly for the purpose of learning the different languages and having the young people serve as translators. A boy named Thomas Savage was on the first return voyage to Jamestown in January 1608. He was 13 at the time. He was sent to live on the north side of the York River with the regional chief and in exchange the chief, Powhatan, sent his son, Namotacke, to live with the English.

Thomas Savage stayed with the indigenous people for three years, but traveled back to Jamestown often, presumably to keep up his English skills. He then served as an interpreter for many several years in a variety of contexts (trading for corn, seeking release of captives, etc.) and settled on the Eastern Shore, which is across the Chesapeake Bay from Jamestown. He became very good friends with the "Indian king" of the Eastern Shore, Debedeavon, also known as the "Laughing King," and was given a neck of land by Debedeavon comprising about 9,000 acres where he and his wife lived. The neck is now called Savage Neck and is about 5 miles south from where I am sitting on the shore of the Chesapeake Bay. Savage was also not the only boy who lived with the indigenous people to learn languages.

There are still many people here on the Eastern Shore named Savage, descendants of Thomas and his wife Hannah, and this family is very likely the oldest continuous lineage of the same name extant in the US. Sorry for the long narrative, but it is a good and true story.

Sources: Ye Kingdome of Accawmacke by Jennings Cropper Wise; The Eastern Shore of Virginia, 1603-1964 by Nora Miller Thurman.

What's the process?

Would they use pictures/drawings and ask the natives what they call each thing?

How about more complicated concepts that can't be represented that way?

I am not sure if it was done before on this subreddit (so please let me know and I will delete my comment), but since some people asked, I compiled here some links to resources to learn some indigenous languages from Canada online. When possible I tried to include the name in the original language, and its English name.

There are so many more languages though, so if you want me to find some resources about another language I will be happy to try to find it for you.

Again, it is always best to ask people from the community themselves to teach you :)

Halq'emeylem (Coast Salish/Sto:lo language): https://itunes.apple.com/us/app/halqemeylem/id467923981?mt=8

Sm'algyax (Coast Tsimshian Language): http://web.unbc.ca/~smalgyax/

Yukon Indigenous Languages: http://cyfn.ca/services/yukon-native-language-centre/ Resources on the languages spoken in Yukon today.

nêhiyawêwin (Plains Cree) : http://apihtawikosisan.com/language-links-2/

Michif (Metis language) : http://apihtawikosisan.com/language-links-2/michif/

Inuktitut (the language spoken by Inuit people) : http://www.tusaalanga.ca/splash

Anishinabemowin (Anishinabe - Algonquin Language) : https://play.google.com/store/apps/details?id=com.languagepal.androidanishinaabemowin&hl=en

Some resources about Kanienkehaka (Mohawk Language) : http://www.omniglot.com/writing/mohawk.htm