Apart from the 1st series of Bushtucker Man mentioned above, there was also the 'Stories of Survival' series; this was entertaining but less informative, being more historical than instructional.
There were also - believe it or not - two PC CD-ROMs with plant ID, travel info, etc.
If you a fancy a laugh and would like to see an excellent Les Hiddins p*sstake, look at the 'All Auusie Adventures with Russell Coight' videos.
Bookwise:
Les Hiddins Bush Tucker Map & Guide (pretty much a 'snack map') - ISBN 0-670-89201
Explore Wild Australia with the Bush Tucker Man - ISBN 0-670-87914-2
Bush Tucker Man - Stories of Exploration and Survival - ISBN 0-7333-0546-6
Bush Tucker Man - Tarnished Heroes - Epic Stories of Bush Survival - ISBN 073330613-6
Bush Tucker Field Guide, ISBN 174117 028 1 and ISBN 0 14 028986 0
All of these are available from ABC books so you might as well have a look at them when you get out there. There are also some other good Australian survival/bushcraft books. Here's my collection:
Useful Wild Plants in Australia, AB & JW Cribb, ISBN 0-7322-2564-7
Wild Food in Australia, AB & JW Cribb, ISBN 0 00 634436 4
(Both old but informative)
Stay Alive, Maurice Dunlevy, ISBN 0 642 05818 0
(Excellent pocket-sized government book - get this!)
Australian Bushcraft, MW Plate, ISBN 7018 0280 4
Australian Bush Survival Skills, Kevin Casey, ISBN 0 9587628 1 3
Book of the Bush, Edward Kynaston, ISBN 0 14 00.4390 X
Bushcraft, Richard Graves, ISBN 0 7100 8862 0
(compulsory reading)
Bush Food (Aboriginal Food and Herbal Medecine), ISBN 1 86302 504 9
(my personal favourite - an excellent book which I cannot recommend too much)
Hope this helps - you'll probably find all of the above are easier to get in Australia itself. I trawled second-hand book stalls and shops for most of them.
Cheers,