From Wikipedia:
日本における漢字表記では濠太剌利とされ、またそこから濠洲(ごうしゅう)とも呼ばれる。「連邦」を付け濠洲連邦(濠洲聯邦)ということもある。「濠」「洲」は常用漢字の「豪」「州」を代用して豪太剌利・豪洲・豪州と書くことも多い。
Your previous confusion of 濠 and 豪 actually makes sense in this context, as 「濠太剌利」「濠洲{ごうしゅう}」「豪洲{ごうしゅう}」are all ateji. Basically the idea is when a non-Chinese foreign word like "Australia" comes to Japan, an attempt is made to phonetically represent the word with kanji, borrowing only the kanji's pronunciations irrespective of their meanings.
The name for Australia was thus first introduced as 「濠太剌利」, shortened to 「濠洲」, and the two kanji, since they are not on the list of 常用漢字 (regular kanji), were later replaced by two other similarly pronounced kanji on that list, 豪 and 州. By the way the さんずい (水部 water radical) makes sense in the context of Australia, because 洲 means or used to mean "land surrounded by water". See the Wikipedia page on 「洲」vs.「州」:
洲とも書く。本来は州が中州を意味したが、州が行政区画も意味するようになったので、さんずいを加えて中州の意味を明らかにした字が洲である。しかし、古くから互いに通用できる。特に現代日本では、洲が常用漢字でないため、意味にかかわらず州と書くことが多い。
These days since 洲 is not on the list and thus not considered a regular kanji, it is replaced by 州 in almost all contexts except holdover place names.
P.S.
As I am discussing the provenance of this word and its historical pronunciation, I am reluctant to render it as 「濠太剌利{オーストラリア}」. I can't find a source but I don't think it was originally pronounced オーストラリア. It is pronounced as such these days for sure but it is very common that country names vary without standardization when first introduced into a new language. 剌利 was probably pronounced ラリ.