As dianod says, van rental is easy in Australia. While there are many hire companies, the vehicles are usually supplied by a relatively small number of rental companies. eg Britz supply vans to literally dozens of hire companies who differentiate themselves by information packs or optional extra equipment etc.
I'd choose a van over train etc - the ability to be flexible is valuable. A tour may be an option if that suits you. You are much more constrained in time spent and what you see - but have the decisions on accommodation and access fees and where to go sorted out for you. You can probably get an Oz travel agent to arrange details such as accommodation ect when you self drive.
I'd recommend using a reputable van hire company with good user feedback. There are some companies who offer older vehicles or who do minimum maintenance or who may be liable to attempt to charge you for minor damage which may have been present already.
Most companies allow one-way travel between selected destinations but a one way fee may be charged. We paid $300 extra to pickup in Adelaide and drop off in Alice Springs (see below), but something as main stream and bidirectional in demand as sydney to Adelaide MAY not incur a one way fee.
One point to be aware of is the tiered insurance scheme. You can possibly choose no insurance (don't do it) or a low rate with immense excess or higher rates with lower excesses or notionally no excess at all. BUT read ALL the fine print. Even the top "no worries" deal we saw did NOT cover everything - single vehicle roll over was not covered - and an event would have cost $3500 or maybe more. How likely is single vehicle roll over?
Varies with vehicle and route, but Britz told us they had had 3 in the last month. Australia is usually a safe enough place to drive - but at dusk and maybe dawn you may meet a kangaroo - and maybe any other time. We almost got one. Sits by roadside as van approaches. Sit wait sit wait sit hop hop hop ... across the van's path. 100 kph to zero squealing stop. Just missed! Whew. On your route you'll not see camels :-). Probably no bulls. Probably will see kangaroos. Pay the $100 extra ! And this still MAY not include immersion damage. Read the fine print.
My wife and I recently did a 9 day drive in a hired camper van from Adelaide to Alice Springs. The van was a Britz supplied one via one of the many Adelaide van hire outlets. The van itself was excellent and Britz standards are good. I did have a few minor disagreements with them over the hiring terms, but they are probably as reputable and trustable as any. (I have no connection of any sort with Britz - but if I was hiring a van in Australia they would be near the top of my list to start with).
On another trip we hired a Mitsubishi Outlander (4 people) from Thrifty and were very happy with their service. A high level behind-the-scenes manager approved an arrangement which made all the difference on our journey, when no other company would do so. (This allowed us to visit Glengarry on outback roads).
There is a company named "Wicked" who paint their vans with large and amusing and/or vulgar slogans. Some of their vans are very low spec with somewhat reduced prices. I'll not say bad things about them in public, but I'd not recommend them. We hired one of their vans once in NZ and while we got a good price with a special deal it cost far more than expected and the van was "interesting" at least. Another company is named "Spaceships" and they also seem to aim at the lower end of the market. I've had no dealings with them.
I'm happy top answer questions on list if appropriate or see my profile page for email address if more appropriate.
Some of our photos - more to come
http://bit.ly/OutbackDreaming <- various
http://bit.ly/OutbackDreaming2013 <- Journey start, Adelaide + more
Braking hard. A closer run thing than it appears:
Small animals: DO NOT swerve. Brake hard as seems safe. Steer straight. Seek to straddle lizards (rare in south). Birds will look after themselves. Veering for a kangaroo is unlikely to be a good idea.
Road Train: You won't see any, probably. Keep left, steer straight, be aware of sudden buffeting at start and end of passing.
If overtaking, allow 1 km to pass !!! (really).