Each morning the islanders are here with the sunrise and in the evenings, long after the sun sets, they linger, not missing a moment of watching us.
When we move on through these eastern islands of Papua New Guinea, there's always more inquisitive locals. They congregate at the back of our "spaceship", in wooden canoes barely staying afloat, four or five children in tow, smiling at us with bright-red, saliva-stained teeth (everyone here chews betel nut until their teeth are mere fleshy, red stumps).
Some days the crew on our cruise ship makes poodles out of balloons for the kids but the warriors - all sinewy, sun-blackened muscle - refuse to miss out, wrapping bright-pink balloons around their fuzzy, black hair.
Early one morning I talk to a girl in a canoe who can speak broken English. She asks for my address in Australia. "Why would you like that?" I ask. "I frite [write] you a letter," she tells me. "But do you have a post office in your village?" I ask. "What is a post office?" she replies.
There are many among the islanders who have never seen white people before, a situation I've never encountered in my travels. To feel like Captain Cook in this ridiculously modern world carries some responsibility. One evening I take a ride with the ship's engineer to a remote village in the Duke of York Islands.
Twenty naked children stand staring at us as we land, one toddler crying in terror, hiding behind his bare-chested mother. They stare at me hard; I feel like the tiny insect specimens we'd dissect and examine under microscopes in high school. Right here I feel I'm responsible for the image - the public relations - of the entire population of white people on Earth.
It's far too much for me to handle. I smile, I wave a little until I feel silly, I say hello 20 or so times in that funny accent we all put on when we travel overseas, then I dip my head self-consciously, avoiding their little eyes. I die on that stage. I crash and burn.
On the boat ride back I chastise myself for my stage fright. I should've sung, I should've danced, I could've been Marlon Brando, Fred Astaire and Jerry Seinfeld rolled into one. But I doubt it mattered; they were probably more interested in the quick-dry boardshorts with the luminous colours I wore and the wristwatch with the little hands that lit up like dull fire in the twilight.
Others among our new friends off the back of our boat have more experience with white folk, like Lionel. "Have there been many visitors through here?" I ask him. "Yes, yes, many," he answers. "We have had two dim dims [white people] here." I ask him when that was. "Not long ago," he says. "Eight years, maybe."
One day, a passenger asks the ship's marine biologist why our new friends don't ever seem to want to go home. "Think about it," he says. "Most of the people round here haven't seen white people before. You imagine if a spaceship landed in your suburb at home and all these funny-looking aliens came out with their funny little gadgets, what do you reckon you'd do?"
I think of the 50 metres and $20 million of gleaming-white painted metal we travel in, the tenders with their noisy outboard motors that take us diving, snorkelling and fishing each day and the helicopter on the top deck that ascends to the heavens every morning.
While it may be us paying good money to observe these people, I can't help wondering who's really on display. As a passenger says to me as we pull in close to a village to see hundreds of children lining the beaches, staring at us with slack jaws: "They watch us watching them; we watch them watching us."
That all this exists in by far the most perfect natural environment I've ever seen says more about Papua New Guinea than anything else. Blue, waveless oceans teem with huge, tasty coral trout and tuna; performing dolphins; rare dugongs; gigantic turtles; unbleached, shockingly colourful coral; even a pod of killer whales (that we swim beside on one extraordinary morning).
If this was anywhere else, Club Med, the Hilton chain, McDonald's and Starbucks would have taken over. We'd be lining up for cabana chairs on these perfect, white-sand beaches and the locals, paid peanuts for wages, would be serving us pina coladas, probably after making a show of climbing coconut trees to fetch the key ingredient.
But this is Papua New Guinea, one of the last great frontiers and, remarkably, one of the least-visited countries. The perceived dangers of its capital, Port Moresby, keep travellers at bay, as does the difficulty in getting in and around (internal air fares are at least five times more expensive than in Australia). To take a luxury boat ride through its most untouched regions, a world away from Port Moresby and any sense of danger beyond a nasty sunburn and a probable case of indigestion, must surely be one of the last great indulgences left to adventure-seeking Australians.
What's more, because North Star Cruises travels through these parts only four times a year (when it's too hot to travel the Kimberley), you don't ever feel as if you're on a conveyor-belt tourist trap, nor will you see another cruise boat.
Our cruise aboard the MV True North will take us from the remote islands of New Ireland off Papua New Guinea's eastern coastline about 1000 kilometres south-west to the mainland at Alotau, in Papua New Guinea's far south.
For a week we'll pass through some of the world's most untouched islands: steaming south through the Duke of York Islands, New Britain, the tiny atolls of the Lusancays and onwards through the D'Entrecasteaux Islands. Never heard of any of them? Don't feel too bad, you're not alone - check the internet and you'll find virtually nothing, although anyone versed in Australian war history will know these regions played a significant role in the Allies' efforts to stop the Japanese advance into Australia during World War II.
In fact, we have a war veteran on board: 88-year-old West Australian Eric Smyth. Several passengers are also here to retrace the footsteps of their fathers, offering them a rare insight into a past they dared never ask about. We even get to dive and snorkel on Japanese tanks and warplanes.
While the region's war history is fascinating, I find myself more captivated by its people. The forests that stretch to the water's edge are full of villages with tribes speaking unique languages (there are almost 900 languages in Papua New Guinea).
For a week I don't see a television antenna, power pole or generator. Many here have never felt cotton against their skin, or worn a pair of Levis; they've never tasted Coca-Cola, or heard a Britney Spears song; they've never downed a Big Mac, or seen Leonardo and Kate confess their undying love for each other in Titanic.
Captain Cook explained their simple pleasures: "Being wholly unacquainted not only with the superfluous but with the necessary conveniences so much sought-after in Europe, they are happy in not knowing the use of them. They live in tranquillity. The earth and sea of their own accord furnish them with all things necessary in life."
And the world they live in bursts with creatures. In terms of volume, variation and the biological significance of flora and fauna, only the Amazon Basin compares. New Guinea is one-ninth the size of Australia but it has just as many mammal types, more than 215 species. It has more than 200 species of frogs, 300 species of reptiles, 300 species of fish, 400,000 insect species, the world's largest butterfly (the Queen Alexandra, which was so big that when it was first collected, it was felled by a shotgun blast), more than 750 species of bird, 20,000 plant species, 3000 types of orchids and 1200 tree species. There are more parrot, pigeon and kingfisher species here than anywhere else on the planet.
This world we travel through is so delicate and precious even the wake from our boat feels like a trespass. The sea remains so calm and mirrored, especially at sunrise and sunset, that I find myself waking each morning in anticipation of first light and the vista it will unveil. When we swim we don't need masks to see the coral, while divers down 50 metres tell us they can clearly see the True North name on their tender bobbing at the surface.
At night, the stars shine so bright it's just my ignorance that stops me learning all the constellations. And when we venture to a village one night by tender, I discover the darkest, quietest place on Earth.
But for me, it's the experiences we share with the people of this land that make this journey.
One morning near Goodenough Island, four children paddle out to us in an overloaded outrigger canoe. It capsizes and we rescue them in our tender. They sit, frightened, at the end of our boat, then pass to us shyly what they were coming to give us: a single pawpaw as a gift.
Near Kokopo, two girls swim out to greet us. A local warrior who'd helped us out for the day waves to them. When a passenger asks him if they're his girlfriends he giggles like a schoolgirl, hiding his face with his huge hands.
Then, I find utopia. At Jacquinot Bay on New Britain's unexplored east coast we chance upon an idyllic scene. We take tenders to the shore, where hundreds of children line a white pebbled beach. When we start waving, they yell a greeting so loud it scares us. They live here beside the beach, next to a thunderous waterfall that gushes from a cave directly into the sea.
We play with the children for hours, swimming beneath the waterfall, sinking low into the sea to feel the saltwater underneath, at least 10 degrees warmer than the fresh water. When it's time to go the children don't want us to leave. I give a little girl my drink bottle; she shows it off to her friends.
They scramble beside us in our tenders. I notice the passenger beside me is crying and the one beside her, too. "I've been using tears as an eye wash on this trip every day," she says. "These kids just make me blubber, look at them, are they really real?"
One day soon, villagers may abandon their traditional ways for the new and experiences like this on board the True North will seem the stuff of science fiction. While the True North visits only a few times a year and varies its itinerary, surely it can't be long before mass-tourism operators discover this wonderland right on our doorstep.
But it's nice to know paradise does still exist on this war-ravaged planet, at least for now, and that paradise looks, smells and tastes just like you thought it would: salty, sweaty, sticky and with the sweet tang of coconut milk.
Craig Tansley travelled courtesy of North Star Cruises.
North Star Cruises provides a return chartered flight out of Cairns to Papua New Guinea. Virgin Blue has a fare to Cairns for $139 from Melbourne and $115 from Sydney, while Jetstar charges $169 from Melbourne and $119 from Sydney. Some flights are non-stop. (Fares are one-way, including tax.)
Australians require a visa for PNG for a stay of up to 60 days, which can be obtained before departure or upon arrival.
North Star Cruises has four seven-night Adventures in Paradise cruises in November. From $9995 a person, which includes all meals, activities and a return chartered flight out of Cairns. Phone (08) 9192 1829 or see northstarcruises.com.au.
Sign up for the Traveller Deals newsletter
Get exclusive travel deals delivered straight to your inbox. Sign up now.