Look for furnished accommodation first, for about the first 3 weeks. You should find this for about $600pw, for a 3 or 4 bed house.
That gives time to look around. It can be very quick to arrange unfurnished property, so 3 weeks me be OK.
I know someone who booked a furnished place for 13 weeks, and got a much reduced rate. But they moved out after 8 weeks, as they finalised a house purchase in that time :)
Long term rentals arranged without viewing can be risky.
What area are you heading for ?
A couple to start with..
Brisbane:
http://www.destinationbrisbane.com.au/
Perth:
http://www.letsgoperth.com/