Currently, Telstra will unlock your iPhone fir free and allow you to use other SIMs
http://exchange.telstra.com.au/?p=7698
The last part of the article is wrong. After getting the phone unlocked, you need to do a "Restore", not just connect through iTunes.
We use TravelSIM when overseas (
http://www.travelsim.net.au/index.php). Previously, we have just used a cheap, no-frills mobile that we have bought outright with a TravelSIM in it. TravelSIM now has the microSIMs in stock suitable for iPhone 4s.