Im new to this site, but basically joined as I am wanting to travel/work in Australia hopefully this year.
My thoughts are to start in Melbourne and work up the coast. Id love for any info on how to get started with the planning/booking etc. Do you recommend going through a company? Or going to a travel agents such as STA and letting them go through it all with you? Im worried about doing it wrong, or missing something out. Im also planning on going alone, so any tips of flying or going alone id love also!!
It is better to go to accredited travel agency to manage your trip well. It is also important to know also if your agent is a reputable one. Check that with the embassy to assist you better.
If you go through a company or a travel agent, you'll have to pay some sort of fee, even if it's just a premium on the airfare. Sorting it out yourself is not that difficult if you're careful.
For a WHV (you're the right age), see https://www.border.gov.au/Trav/Visa-1/417- which is the Australian immigration site. They have a FAQ page too so there's further help. Once you have your visa sorted, the air tickets are straightforward.
For air flights, try Skyscanner. If you're not bothered about the frills, from Bangkok, Singapore or Kuala Lumpur, the budget airlines of Jetstar, Tiger Air and Air Asia can get you to Australia and surely there's a budget airline that'll get you from Britain to SE Asia.
For jobs, try Googling "Jobs in Australia"! http://www.seek.com.au/ is one site that should come up and there will certainly be more.
Enjoy your planning and enjoy Oz.
Sadly the last attempt at proper budget flights from the UK to SE Asia, by AirAsiaX, closed a few years ago. I used them a few times, great service, but they said it didn't pay and ended both their London-KL and Paris-KL routes. I don't know why they didn't just increase the prices, as they were the cheapest carrier by quite some margin, so there appeared to be some wiggle room.
Happily the "kangaroo route" is well served and competitive. As Borisborough says a search on Skyscanner makes it easy to do it yourself, particularly when it's a straightforward there and back to Oz. Probably cheapest to get a return ticket for the full route rather than trying to use the budget carriers for the second half, as doing the first half by traditional carrier will be almost as much as their full fare to Oz.
You could always talk it through with STA or Trailfinders etc and get their advice, then make your mind up whether they add value over doing it yourself.
Re tips for doing it alone. You could look for a travel buddy on here who's going at the same time, meet up and make friends well before you go, and do the scary first couple of weeks together. Or, staying in hostels you'll meet plenty of people doing the same thing as you, all the time, so it will be fine. :-)