Hi Brad,
Personally when I drive between Perth and Cairns or in return (which I've done a few times), I just head straight through the centre. So Cairns, Townsville, Winton, Boulia, (Plenty Hwy/Donohue Hwy), Gemtree, Alice Springs, Ayers Rock, (Great Central Rd), Laverton, Kalgoorlie, Perth. It's an easy enough 6-7 day drive, bush camping en-route.
The Nullabor is a pretty boring drive, so personally I'd skip that, but that may be because I've done it too many times.
The Savanah way is pretty decent, but even 10-12 days isn't really enough time if you plan on seeing the sights. The section between Boroloola and Roper River is well worth it - especially the drive into the northern lost city. An explore around the Eastern Gregory NP is also pretty good. Of course once you get into the Kimberly, you need 4-5 weeks to enjoy the place.
Anyhow, I hope the info helps...........
John