It is a short linguistic journey from Australia to Aussie to Ozzie to Oz. Fortuitously, the Land of Oz is associated with beauty and magic and enchantment, precisely the qualities that Australia is known for. So the name stuck.