The short answer is "people turn out to be pretty good at learning languages". Immersion learning is a thing that works pretty well; keep in mind that babies come into the world without an existing translator, and they turn out all right.

Modern linguists (most notably Dan Everett, who studied Brazil's Pirahã language) have developed a pretty structured method called "monolingual demonstration" (there's a video here) in which the linguist attempts to learn a language's vocabulary and study its grammar at the same time. But if your only goal is to be understood for purposes like trade and conquest, you only really need some nouns and verbs ("Men bring gold, trade pots. Men no bring gold, men die."). You'll sound like an idiot because you don't have the grammar right, but they'll get the general drift.

As for your specific examples: "Aboriginal" is not a language. Australia has (at least by European and East Asian standards) a surprisingly large number of native languages. Wikipedia even lists 27 distinct families of languages. So if someone here is familiar with Australian colonial history (and I'm not that someone) you'd probably need to specify which encounter you're thinking of in order to get an answer.

Japanese is a real language, but it was to my knowledge never isolated from English-speakers; certainly by modern times, even if there was no bilingual Japanese and English speaker, there would have been some possible chain of translators. By the time of Perry's "expedition", both Chinese and Dutch were well-enough known by both sides to serve as intermediate languages for negotiations between American and Japanese officials. (Source: De-min Tao's fascinating article here)

If you're an American, you probably know the story of Squanto, the Patuxet man who helped the Mayflower colonists survive. He also worked for them as a translator because (and this is perhaps less well-known) he already spoke English when the colonists arrived. That's because he had been kidnapped and sold into slavery by Englishmen earlier in his life. This is, incidentally, another way people have learned new languages: figure it out now or you'll be beaten half to death.

So maybe there's another short answer: isolation is a lot less common than we might expect.

People who want to communicate can manage to communicate. Obviously, deep abstract conversations are going to be difficult at first, but easier stuff can be communicated easily. You have to remember that a good deal of communication is non-verbal, so we don't understand each other only with words. When you don't share a language, you rely more on that. Basically: point, point and point.

You learn a language better when you NEED to speak it, and aren't just trying to pass Spanish 101 in High School. If you are surrounded by people who speak it, you'll pick it up much faster than usual, and you'll learn what you need in a day to day basis, not necessarily like you would in a formal language class. And once you can communicate your basic needs, you just keep learning more easily.

When the Portuguese were navigating around Africa, they knew they would need interpreters for trading, plus they could get information about their nations by talking to them. So they would capture a few people, take them back to Portugal where they would learn the language, and then come back with them as interpreters, having learnt about their culture.

This was also done while exploring America. The case of Hernán Cortés was a little different, though, because he actually found two Spaniards living in Yucatán when he arrived there. The two men, one of them a friar, had been in a shipwreck, but had survived and ended up in the peninsula (with a few more survivors who were killed, died of illnesses or had been enslaved.) They escaped their first captors and ended up with another Maya tribe. While one of them (Gonzalo Guerrero) married a Maya woman and became a warrior, the friar Gerónimo de Aguilar wasn't feeling it and so he was kept as a slave. They had lived there for quite a few years when Cortés arrived, so they learnt the language because of a basic need to communicate, and so Cortés used Gerónimo de Aguilar as an interpreter from Maya to Spanish.

You might have heard that la Malinche, a Nahua woman (so speaker of Nahuatl) who had been captured by the Mayans (so she learnt Maya), was Cortés' translator. At first, since la Malinche didn't speak Spanish, she translated from Nahuatl to Maya and Gerónimo de Aguilar between Maya and Spanish. Eventually she learnt Spanish and she translated by herself.

There's a good series of articles about the interpreting profession by Christine Addams in AIIC's website: here. There's one about the first interpreters in North America, about La Malinche, the Portuguese in Africa, the Iberian peninsula during the Moorish ocupation, Jesuits in Japan, the Ottoman Empire and a few more.