Moin Thomix,
meine Erfahrungen in/aus Westaustralien (WA), für die östlichen Provinzen gilt das vielleicht auch(?):
Unterkunft:
Günstig sind Backpackerhostels, die in WA auch recht sauber waren. Die Preise beginnen so bei 20$ pro Nase und Nacht. Bei anderen Unterkünften gilt sicher: "the sky is the limit". Da ich alleine gereist bin, kenne ich eher die Hostels als Guest Houses. Auf Campingplätzen gibt es auch diese semi-fest installierten Wohnwagen, wo Ihr auch eine Anlage für Euch allein mieten könnt.
Allgemein, hier hilft eher ein Blick in den Reiseführer ("Stefan Loose" oder "lonely planet").
Weiterhin:
Ein Bier: 7.50$ bis 8.70$ 
Ein Glas Wein: ab 6$
Eine Flasche Wein: ab 26$
(Preise von "Little Creatures")
Mietwagen(?):
Wenn (für Euch) bei Mobilität nicht der Preis ausschlaggebend ist, rate ich zum Mietwagen. Ihr habt ohnehin wenig Zeit, seid mit einem Mietwagen flexibler und könnt Euch alles "in your time" ansehen. Wenn Ihr den Wagen bei einer anderen Filiale abgeben wollt - Mieten in Brisbane und Abgeben in Cairns -, kann es ggf. noch einen Aufschlag dafür geben; das kann aber unterschiedlich sein und ist zu hinterfragen.
Als Norddeutscher bin ich schon immer auf ein Auto angewiesen gewesen und ich liebe es, auf diese Weise unterwegs zu sein. Das hat was von "Freiheit und Abenteuer". :)) Ich habe pro Tag zwischen 65 und 80$ bezahlt; inklusive Versicherung, was sich gleich zweimal richtig gelohnt hat... 
Benzin ist recht günstig: In Perth zahlt man für den Liter Normal um 1.09$ (60 bis 70 Eurocents). Im Osten soll es sogar günstiger sein.
Gute Reise!
Steffen