Well, technically it is a rhetorical question - and I can't see why anyone would think it uniquely Australian!

Even though it's a perfectly normal phrase to me as an Australian, I've done a news/blog search of the pattern. It turns out that the structure is regular English, and not particular to any specific country. As Hilary has said, it's basically a rhetorical question. You can understand it as a declaration, such as "How lovely!" or "What awful weather!" I suggest accepting this pattern as-is. For your other options in the comments, adding "by" simply means you need a gerund. The other option for the sentence is, "What better way to celebrate Australia Day than to sing the anthem." You can also use "than with", eg. "than with the anthem". "What would be a better way..." is the beginning of a question, eg. you think that singing the national anthem is NOT a good idea, and you want other options. So, the meaning changes!

You heard correctly. What better way to celebrate Australia Day than having some mates around for a BBQ. I believe it is just an Aussie expression, usually said with an exaggerated Aussie accent :)

It's not an Australian expression. It's standard English.