Whilst you can purchase the Garmin Edge 800 bundled with Garmin Australia Topo maps on a card (not transferable to your computer) there are other options in terms of mapping, in this case the Open Street Map Australia maps (OSMAustralia).
The OSMAustralia maps can be downloaded here. There is an OSM map for each state, which it is stated are updated daily at around 2:00 AM AEST, however on the day I wrote this page (March 7, 2011) that last update was dated February 8, 2011.
That said, the process of downloading them and installing them on your Garmin Edge 800 was pretty straight forward for me on the Macintosh. I haven’t tried this on a PC I am sorry so cannot advise if the same process applies or not.
Anyway what I did was download the state zip file, Western Australia in my case, unzipped the file on my MacBook Pro and then copied the two *.img files straight over to the directory on the Garmin Edge 800 where the gmapbmap.img file resides, disconnected my Garmin Edge 800, turned it back on and bingo the OSMAustralia maps where installed and enabled along with, in my case the Garmin Topo map.
I haven’t yet played with the OSMAustralia maps, but it is good to have a free, potentially daily updated map set for the Edge.