Something that I've always wondered about is how did the first few groups of European explorers figure out how to communicate with the natives in regions that had previously had no communication with the West?
I'm guessing if you were exploring Florida and had someone in your group that knew a language native to Cuba, you could probably find someone in the area who knew that language. And if you were British first exploring an area that had had Spanish presence, you would probably find a native who knew Spanish, so even if no one in your group knew a language from the area, you could probably still communicate.
How did they start this?
There's always room for discussion, but perhaps the section Cross-cultural communication and lingua francas from our FAQ will answer your inquiry.