Hi
I travelled the route cairns-brisbane a few times when i was there years ago and i did it by bus, stopping in townsville, airlie beach etc...dont worry! I also went to sydney and melbourne by train/plane and i lived near byron bay in a place called Lismore.
Dont worry about booking any accomodation in advance, apart from your 1st and maybe 2nd night. Backpackers are not places that u usually book in advance, you just turn up and ask for a room on the day. Rooms are very cheap, only a few dollars if you are sharing with others (meaning u share a room with other people u dont know but have yr own bunkbed), and this is the best way to meet young people from all over the world! You will meet lots of interesting characters and people that can help along the way. They are all doing the same thing as you, discovering places and following the same route as you!
The most economical method and most popular of travelling to places is by bus (Greyhound), which is just like National Express.
If you have any more questions about it get back to me.