Until recently I've been planning this trip as best I could using the internet and a country map of Australia that I purchased on a previous trip to the continent. The map was enough to get me started, but not enough to adequately prepare for an unsupported bicycle tour. My original map lacked any indication of rest stops, and other such bicycle-important items. However, I eventually found an excellent source for maps, the Royal Automobile Association of Australia:
http://www.raa.net/shop_products.asp?SecID=56&CatID=4
These maps are a great resource for the touring cyclist, including accurate distance markings, rest stops, road houses, Railway sidings, etc. For this particular trip I ordered the South Australia and Northern Territories State Road Maps, as well as the Outback South Australia map.
You can contact the RAA directly by writing to them at:
Automobile Association of the Northern Territory Inc.
GPO Box 2584
Darwin NT 0801
Australia