During the age of the explorers and conquest in the New World and the Pacific, peoples were encountering one another without (I think) any possibility of previous linguistic overlap. So how did Columbus, Cortez, Magellan, and so on, manage to communicate with the locals? What do we know about the process? What did they start with? How long did it take? Who tended to do the learning?

I'm really curious about this issue in any historical context, but I thought the explorers and conquistadores made a good focus point. If you know about the issue in classical antiquity or some other time, I'd love to learn!