I got a cheapie from THINK mobile.
$12 a month plan with $12 calls included for 12 months plus $20 for a Nokia5000 handset. The handset is cheap but seems solid enough and does all that I want from a basic phone.
Some phones you can get free on a 6 month $12 plan.
http://www.thinkmobile.com.au/plans/12plan/index.htm