Im Januar ist Cairns vielleicht keine so gute Option - da würde ich maximal bis Brisbane nördlich an der Ostküste hochgehen.
Je nachdem, wann im Januar du nach Australien kommst, solltest du im Hinterkopf haben, dass zu der Zeit Sommerferien dort sind und es an vielen Stellen sehr voll sein kann. Entspannter wird es erst nach dem Australia Day (26. 1.), wenn die Kids wieder zur Schule gehen.
Ansonsten bietet es sich an der Ostküste an, den "Short Hop Pass" von Greyhound zu kaufen, kostet für die STrecke Sydney-Melbourne (oder umgekehrt) z.B. 99$, Melbourne -Brisbane 219$. Mit dem Pass kannst du beliebig oft ein- und aussteigen, musst aber immer in eine Richtung fahren. Alternativ gibt es auch Kilometer-Pässe - da brauchst du aber mindestens 2.000 km, denn von Brisbane-Melbourne sind es schon rund 1.800 km
http://www.greyhound.com.au/passes Allerdings ist die Streckenführung aus meiner Sicht nicht wirklich optimal, weil du z.B. von Sydney nach Melbourne über Canberra musst und nicht die tolle Küste entlang fahren kannst - siehe Streckenplan von Greyhound
http://www.greyhound.com.au/Clients/GREYHOUNDNEW/documents/pdfs/Network-Map.pdfÜberleg mal, ob nicht ein billiger Mietwagen eine Option wäre...
Jedenfalls bietet die Strecke zwischen Melbourne (oder auch ab Adelaide, inkl. Kangaroo Island) bis Brisbane so viel, dass 4 Wochen kaum reichen, wenn du an manchen Orten auch mal ein, zwei Tage bleiben willst. Ich bin die Strecke schon ein paar Mal gefahren - zuletzt dieses Jahr im Januar/Februar. Zuerst
Adelaide-Melbourne, dann einen Abstecher nach Tasmanien, anschließend
Melbourne-Sydney (dann 5 Wochen nach Neuseeland) und zum Schluss noch
Brisbane-Sydney. Was es auf der Strecke zu sehen gibt, kannst du gerne in meinem Blog nachlesen
https://fernwehheilen.wordpress.com/2015/01/14/14-01-die-wende/.
Tasmanien wäre evtl. auch noch eine Überlegung wert.