Where the Dog Sits on the Tucker Box, Five Miles from Gundagai. Got a great old 78 recording of it by Jim Davidson and the ABC Orchestra from Sydney in the late '30s.
There’s been a few corkers already which you can’t beat, and the three specifcially I love if I want to get all patriotic are:
Sounds of Then (This Is Australia) by Gangajang
True Blue by John Williamson
Land Down Under by Men at Work
I can also suggest the following,
Anything by Slim Dusty - especially The Pub with no Beer, and I Love To Have A Beer With Duncan If you search for music by Slim watch out though he was an incredibly prolific song writer.
A walk in the Light Green (I was only Nineteen) by **Little River Band ** - 100% guaranteed to be sung loudly by all Australian males in hearing distance when selected on the jukebox in the pub.
Any number of songs by John Williamson, obviously including *True Blue * mentioned above.
Lastly one that you will probably find very difficult to locate but classic Australian
I Made A Hundred In The Backyard At Mum’s by Greg Champion
A Walk in the Light Green (I was only Nineteen) is by Redgum, not LRB. Their I’ve been to Bali too is another very Australian song.
Two bands as yet unmentioned are The Angels and Weddings Parties Anything. A Tale They Won’t Believe or Under the Clocks would be good film backing.
Another that might suit is Bernard Bolan, a Barrister/Folk Artist from the 70’s. Some of his stuff is still available, and my personal favorite is “The Rose Bay Ferry”.
Check him out here - http://www.folkaustralia.com/BernardBolan/bio.html
Edited to add the URL.
I Am Australian, by Rai Thistlewayte (from Thirsty Merc). It was used in an ad for Telstra, which may be a bloodsucking company of dubious honesty, do at least have some good ads sometimes.
It’s by the Seekers.
Another that’s been used by a corporate giant (Qantas), I still Call Australia Home by Peter Allen, sung here by the National Boys Choir.
The Triffids were a great, underrated Australian band… you could try something from Treeless Plain maybe, like Hell of a Summer…
I know, but the version I like best and am recommending is the one by Rai Thistlewayte.
Tina Turner is not australian, but the following songs are quintessentially associated with Australia in my mind:
We Don’t Need Another Hero (from Mad Max Beyond Thunderdome) and
You’re Simply the Best - used as a theme tune for Aussie Rugby League.
Real Australian songs by real Aussie artists are
Jimmy Barnes: Working Class Man
Australian Crawl: Reckless
oh, and Physical 
Si
Olivia Newton-John was born in England, though she did move to Melbourne as a young girl, so she’s not exactly a “real Aussie”.
What, and Jimmy Barnes is a true blue?
You’re right – he moved to Australia at about the same age as Olivia NJ did.
I notice that everyone says Aussie, never “Ocker”. Is the latter term offensive?
'Cause I like to call 'em Ockers.
Oh, and “Land Down Under”.
ETA: Don’t mean to be offensive, I’m a bit drunk at the moment, I’m sure you’ll understand. Ya ockers.
The two terms are not interchangeable. An “ocker” (itself slightly old fashioned now) is a rough-around-the-edges, beer-and-football bloke. Kinda the opposite of a metrosexual.
Americans and others should avoid using it to mean people/guys in general, just like “mates” isn’t used here in that way. it’s not offensive at all, but it just sounds odd. A bit like if I were to refer to a bunch of Americans as “pard’ners”.
Air Supply?
The Coke jingle from the film “The Coca Cola Kid .”
thwartme
The Herd do a really good version of I was Only Nineteen.
Adelaide by Ben Folds if you happened to visit.
Yothu Yindi’s version of Jailbreak.
That’s the one I thought of too! 
Check out the Go Betweens. Especially the Liberty Belle and the Black Diamond Express album. Their lead singer sadly died last year just as he was on the verge of actually making some money.
What music screams “Australia” to you?
Well how about Monty Python’s Philosophers Song