Essentially you are applying for credit if you buy a phone on a plan and they will do credit checks and such to ensure you can pay it back. I'm not sure of your residency status however there may be a problem if you are not a resident of Australia. Should that not be an issue you simply need as many forms of addentification that you can muster. Go to any local store, select a phone and a plan and if approved and they have stock you should be able to walk out the door with your shiny new device.
Edit: The link below may be of some benefit as it gives you the information required for identification.
It might be good to just buy the phone you want. Then pick either a prepaid or postpaid (contact) SIM only deal.
Prepaid would likely have little credit issues for obvious reasons.