There are three main (not virtual) networks in Australia -- Telstra, Optus, and Vodafone. Telstra is the best network, Optus is #2, and Vodafone has been sadly lagging behind in a distant third place. Recently, Vodafone has stepped up its game a bit.
One issue you could run into is registration. Some places don't ask for any ID, most will happily accept a foreign passport, and one or two places demand proof of residency. If you run into Group 3, argue a little and then vote with your feet. The next store will sell you.
The best place to learn about Australian cellular is:
http://forums.whirlpool.net.au/forum/114
Most SIMs are scripted to automatically install the appropriate access point on an iPhone. If you run into the exception, you can get the configurations here:
http://www.unlockit.co.nz/mobilesettings/