Australian citizens definitely used to need a visa to enter the Republic of Georgia a few years back.
Then last year (2010) I entered by land from Turkey and was given a 360-day stamp at the border with no visa necessary.
Now (July 2011) the Australian Government Department of Foreign Affairs and Trade website says:
If you are an Australian citizen, you need a visa to visit Armenia, Azerbaijan, Belarus, Georgia and Moldova.
Is this a poorly maintained website or has Georgia really flipflopped on the visa rules for Australian citizens?