This involves a bit of suspended disbelief;
PoD: Dutch revolt drains Spanish, English, and Dutch energy, resources, and manpower...
ITTL, Courland starts an overseas trading company, utilizing the Dutch style joint-stock companies with a few Polish Nobles and German states putting their stock into the company. As OTL, they seize a few minor possessions in Africa and the Caribbean, and start an India company, setting up shop in the early 1670s.
When Polish ships begin hearing tales of a strange southern continent, and notice odd things when travelling in the waters around the East Indies, Poland-Lithuania commissions an exploration of the area, revealing the nice habitable bits of Australia. Though other states claim the area, France is still too divided by *Fronde to settle the region, England has Republican hold-out headaches to deal with, and the Netherlands is overall weaker and has a smaller population due to butterflies impacting the Huguenot Wars and Thirty Years war.
Serendipitously, Ruthenia is lost to a revolt and Russia steps in to take the area, leading to a lot of fleeing Polish nobles and peasants, some of which head for Australia.
Saxony/Prussia/Austria and Russia then begin wars eating at the Polish borders, displacing and exiling many Poles to the *Australia.
As the Motherland's power weakens, the Polish Australia breaks away, fending off invasions from it's neighbors, even gaining some territory.
Poland and Lithuania eventually end up vassalized to *German state and Russia respectively, and under the oppressive policies, many Poles leave for Polish Australia.
By the 19th Century, Poles make up the majority of Australia, enough that the other colonies often speak Polish as a second language.
Eventually, either through war, or peaceful integration, Australia is united under this Polish Exile State.
There you go.
