There is very little difference between the broadside and oral versions of 'Maids of Australia'. It was printed in the second half of the 19th century by Such of London, Pearson of Manchester, the Glasgow Poet's Box and Sanderson of Edinburgh and there is no reason to suppose that it is any older than the earliest of these printings.
Some show signs of having come from oral tradition so I will conduct a study of all versions and get back to you with my findings. Personally I quite like the song but that's neither here nor there.

Unfortunately we can't pinpoint the date of any of these printings to within a decade. Sod's law: Nearly all of the Glasgow Poet's Box slips are dated very precisely, all except this one, grrrrh!

Anyway, just to be going on with here is the GPB version.

One morning I strolled by the Oldberry banks,
Where the maids of Australia play their wild pranks,
Beneath the wild bushes I laid myself down,
All looking delighted and chanted around,
In the forests of happy Australia,
Where the maidens are handsome and gay.

I gazed with delight at this beautiful scene,
With the forests so wild and the trees ever green;
Then a beautiful damsel to me did appear,
To the banks of the river she quickly drew near,
She was a native of happy Australia,
Where the maidens are happy and gay.

She plunged into the river without fear or dread,
And her lily-white limbs she so neatly spread;
Her hair hung in ringlets, its colour was black--
"Don't you see, sir," said she, "how I float on my back,
On the streams of my native Australia,
Where the maidens are handsome and gay."

She swam till exhausted, and near to the brink,
"Assistance," she cried, "or I fear I will sink;"
Like lightning I flew and took hold of her hand,
She instantly tripped and fell back on the sand,
And I entered the bush of Australia,
With this maiden so handsome and gay.

I gazed and I toiled with the lightest of glee,
She was the fairest Australian I ever did see;
Long time did my head on her bosom recline,
Till the sun in the west did its limits resign,
And I left that fair maid in Australia,
Where the maidens are handsome and gay.

With this version at least there can be no question about the setting. Australian Tourist Board advertisement? Without going into offensive detail it's pretty obvious the broadside writer had never been to Australia and his informants were also somewhat misled. Songs of this type with very obvious sexual euphemisms abound in street literature, a lot of them printed in Ireland by Goggin of Limerick, long before this one.