Apple now have links to two of the major carriers in Australia from their Australian iPhone website. Telstra are, not surprisingly, missing from this list.

My preference is Vodafone so I clicked through and pre-registered with them. You can do so too at their pre-registration page – and apparently a sales rep will call you back. I’m currently with them on the $79 cap, so I should be able to carry right on and hopefully get the best data plan possible. More details after a Sales person calls me.