As was mentioned already the major two carriers in Australia are Vodafone and Telstra. Also there are two smaller ones like Virgin and Optus. While the smaller carriers offer some times cheap plans, their coverage is lacking.
When I was in Australia in October 2011 I decided to go with Telstra. I don't remember exactly why, but maybe because they were cheaper.
Data plan was an important factor for me and I was very happy with their service.
I bought the sim for 30AUD which you get back as balance on your account. For the same amout I bought a plan that included data & call minutes. The plan was similar to what they call now Pre Paid Cap Encore, which means you get $250 credit calls (which run out quick because of high minute tariff) and 500MB of data. You can see additional details here: http://www.telstra.com.au/mobile/prepaid/prepaid-offers/
Don't be tempted to buy the sim at the airport from Vodafone -- at the city they cost less.