Best bet for the 'outback' is do as many english backpackers do, is buy a cheap car (aka that Top Gear special in the states!) & sell it at the end of the trip. But learn to respect the desert, it doesn't respect human life in the heat of the day. Or the cold of the night.
Agreed, most places are separated by the hundreds or thousands of km's and mother nature is not very kind in the outback or in the bush and people dieing out there is not uncommon if you have not got the right car or and equipment.
If you choose to get a cheapo car and drive to places, make sure you have the following:
An up to date map, a well maintained car with spare fluids and tools to fix it if something happens, plenty of food and water, you can not have enough water, especially in the summer months when temperatures can be more than 110'F take a first aid kit and other essentials and spare fuel too.
When driving between centers, stick to the main roads, observe all signs and warnings, plan your journeys well in advance, when driving through the country turn your lights on, especially at dawn and dusk and watch out for kangaroos in those times too. They can write off a car and kill you, they are extremely dangerous to motorists.
And if you end up driving through the outback, especially in summer, and the car breaks down, for Gods sake do not leave the car! You will find mobile coverage does not exist in most of the country and I wouldn't rely on that for help either, notify someone of your plans and take a CB radio with you.
Greyhound coaches run coach services to many parts of the country, check out their website and try traveling that way.
The Ghan runs between Adelaide and Darwin and is the best way to see the outback, you don't have to do the whole journey, you can just go as far as Alice Springs in the red centre and go see Ayers Rock or fly to one of the state captials.
Flying is cheaper and quicker in all circumstances and most flights, particularly Melbourne to Adelaide, Canberra, Hobart and Sydney fly low enough that you can see the landscape below.
Also if you want to see railway things, check to see where there are railway museums, most cities and states have them and they are great to see.
But yeah, losts of people travel around so if you do things the right way and you do them safely you can see lots of great things out there.
Best of luck to ya!