Havent been home in a while (to bloody long, but thats another story) but my little brother says the main cell providers are telstra, optus, 3, vodafone, virgin.

He says if you are in a decently built up area - 3 is probably the best - but you may run into the 3 sim issue with the n900