Hmmm... georeferenced maps for Australia. About all I can say is that there are more than there are for Tierra del Fuego. There was some excitement late last year when Microsoft's Pocket Streets and Trips was promoted as having Australian maps. That seems to have fizzled. I guess some MS drone mistyped 'Austria'. (sigh)
Hardware. Tough call. I have an Emtac which is small and light and reasonably-priced and robust, has never let me down. Best you head over to
GPSPassion for comparative reviews.
Software for Australia, well, it is a bit tough to go past
Fugawi or
OziExplorerCE. I know definitely OziExplorerCE and I think probably Fugawi supports the georeferenced Natmap raster series, topographical maps that cover
all of Australia in considerable detail. Not only that, but OziExplorerCE (and again I think Fugawi) also supports the georeferenced
Sydway and Melway street directories.
I suggest you read the OziExplorer site
very thoroughly. You will glean much information from it on what is 'do-able' Downunder.
I'd also recommend checking out
Dale DePriest's page for some info on the basics.
EDIT: I should have said, all the above software solutions are for
raster maps (basically, scanned maps that have been georeferenced). If you want turn-by-turn routing, hard to go past Navman's stuff.
This link is for a bundled GPS receiver and their excellent SmartST software/map package (SmartST maps are the Sensis
vector ones you may have seen on the web e.g. Whereis). But I'm reliably told that if you talk with Navman, the SmartST software/maps have a separate SKU so you can buy them seperately should you wish to source your own GPSr.