Right!
The west and north
OK, so we can plausibly dispense with subdivisions of Western Australia and the Northern Territory. Both have been proposed- acted upon, briefly, in the case of the Territory- but there's simply no population base for them.
Barring the physical transformation of large parts of Western Australia via the kind of irrigation scheme that seems more likely to destroy the landscape than save it, the demographic case for a single large Western State seems set to remain. The Northern Territory will, at some point, likely become a state- but it will be vastly, disproportionately small and weak even compared to US states like Wyoming.
This is also, incidentally, why I don't think you'll ever see an Australian equivalent of Nunavut- the Territory is by far the area of Australia with the highest proportion of Indigenous inhabitants, and they're not a majority. Australian politics being what they are, I doubt that you'd ever see the necessary support from non-Indigenous Aussies for such a state, even if it was backed by the majority of indigenous people (I don't believe that it is.) If, for the sake of argument you did carve out a piece of the territory to be the 'Indigenous state' (and there are many, many problems with that, not least that the vast majority of aboriginals have no connection to that Country,) it is the only possible scenario where I can imagine two states being carved out of the Territory. That is to say, I simply can't imagine a government that thinks its politically possible to increase indigenous representation in the Federal Government while keeping the white inhabitants of the region in a Territory.
Moving east.
There's not much chance of dividing South Australia; the proposals for a 'Princeland' between that colony and Victoria never had much support in the 1860s and that was the high point. Victoria's similar. The idea for a state around the Riverina in the Murray-Darling is a non-starter; it only got any traction in the 2000s when it finally became inescapably clear that water management was going to be a major issue, and it was largely popular with people who wanted to avoid the regulation of the rivers. Even if they had successfully built up any kind of popular movement- which they didn't- there's no way Victoria, South Australia or New South Wales were going to stomach the hijacking of a vital resource artery by climate-change denying landowners.
New South Wales- alright, here's your silver medal, the second-most likely place to give you a new state. New England- in the north of the state- has had a secession movement for a good century, and even had a referendum on statehood in the 1960s. It lost fairly narrowly, too, with 54 percent against- in part because the NSW state government cleverly drew the map of the proposed state so it would include the city of Newcastle, which had no intention of giving up its economic links with the south and interior of NSW. If that map gets drawn differently, which it probably does if the referendum gets held in the 1920s or 1930s, well, there's your state. It'll be an odd one- the only Aussie state with no clear capital. Guaranteed senators for the Country (or later, the National) party I'd imagine. Sort of an Aussie equivalent to those Republican strongholds in the Midwest- though if they include the Hunter Valley it'll have better wine than the Dakotas... A lot will depend on if it gets a corridor to the sea (maybe Coffs Harbor?), because I'd expect that port to boom. If Newcastle does end up as part of the state, it'll be the capital of necessity- which would lead to an interesting tension where the capital really doesn't want to be part of the state, but also plays too big a role in its politics to be brushed aside in the manner of liberal cities in the Midwest. New England would probably be a Labor/National area, with the Liberals not getting much of a look in. The other political Aussies might disagree with me there though.
While we're in NSW, I think we can take a moment to rule out statehood for Greater Sydney (and Greater Melbourne, for that matter.) This sometimes gets proposed, but I think people make the mistake of drawing too many analogues with the American Union- you know, statehood for NYC and so on. The relationship between Melbourne and Victoria, and between Sydney and NSW is very different from NYC and New York. The rural hinterlands and smaller cities might not like the capitals, and vice versa. But they can't be separated politically without all manner of regulatory problems that would potentially cripple the economies of both the new and old states.
Queensland! The gold medal. Going right back to the 1870s you had an extremely strong movement to divide the state. In fact, running the odds, it's probably quite surprising that we only have one state north of NSW and not three. Four, of course, if you count New England! A tripartite division of Queensland was very possible, and perhaps even likely. Central Queensland's separation movement really got going in the 1890s, and was weakened by Federation- since it lost the right to appeal to the British government, which had made sympathetic noises. They key to breaking it off is in the even more popular movement to break of Northern Queensland, which had been an ongoing project since the 1850s. The pressure point here is immigration; the Far North was dependent upon plantations served by non-white labour
trafficked recruited from the Pacific Islands. This was a fundamentally different economic model from the rest of the state. Right through the second half of the nineteenth century it caused major arguments in the Queensland press and legislature (and throughout the rest of Australasia.) On the one hand you had a coalition of anti-immigrant factions- the nascent Labour movement, missionary societies appalled at the mistreatment of laborers, militant republicans and proto nationalists like the
Bulletin writers and all manner of concerned citizens worried that non-white people would spread south from Cairns and, bluntly, attack your daughters. On the other, the settler communities in the north who were making good money out of the trade and plantations, and didn't think that their way of life could survive without foreign laborers- it was, of course, scientifically impossible for white people to work in the tropical heat in the same conditions as the islanders.* In the end, the depression of the 1890s probably ended the movement; before then the tide was shifting against the use of foreign Labour and faced with a hostile government in Brisbane the north might have successfully petitioned London to divide the state. But the depression saw the anti-migrant restrictions eased for a decade, and after that Federation came- which, as I said, stripped London of its role in determining the boundaries but also saw the immediate passing of an act calling for the deportation of the islanders. After that, though the separation movement's been quietly popular ever since, it's never had the economic case or the political might to get anywhere.
But if it does, then you see a state stretching from, let's say Townsville north. The weakened rump-Queensland is also likely to lose Central Queensland at this moment, as those communities would jump on the British reassessment of the boundaries too. They're likely to have a capital at Rockhampton. That leaves you with the south of the state, even more dominated by Brisbane (though that's likely to be a smaller city in this timeline as it won't be the natural home of the mining companies in the north-east anymore.)
Overseas
Ignore wiki. Timor-Leste and Papua New Guinea had no prospect of becoming states. The island group that did have a shot- and that's basically ignored in wikipedia- is Fiji, whose European community was very interested in being incorporated into Australia or New Zealand in the 1890s. Fiji was not self-governing- the governor there (formally of the Western Pacific High Commission) saw his job as including the duty to protect the locals form annexation to Australasia, as it was expected that the settler colonies would destroy the Fijian population and steal what land was left. Granted, the WPHC didn't exactly treat the islanders well themselves but they probably weren't wrong that things would have got
even worse if Fiji had been annexed. New Zealand probably came closer to taking the island group- there's a letter to London from the early 1900s where a staffer in Fiji warns Joseph Chamberlain that the islands had to be kept form the hands of Richard Seddon and his 'parliamentary hoodlums,' but many of the leaders of the Australian Federation movement thought that Fiji would become a state.
If it does, you're going to have a very nasty state of affairs- a state dominated by a white plantation elite, that unlike North Queensland is also a demographic minority. That's going to lead to bad things when decolonisation hits the Pacific. I'd expect to see more white people move into the islands, and perhaps- depending on what type of White Australia regime is in place- a serious attempt to co-opt the Fijian Indian population into supporting statehood.
The other big one: New Zealand.
Now, I disagree with most people in that I think there was still an outside chance at New Zealand statehood as late as the 1890s. Some of the explanations for why it was impossible are straight up nonsense, especially the idea that the Treaty of Waitangi would be insurmountable. Ignoring the fact that at this time the New Zealand position was that the Treaty was a 'simple nullity,' there is no evidence at all that the Australian states thought that the Maori should be treated in the same way as their own indigenous populations and in fact the first Australian government was prepared (and thought it important) to make any necessary constitutional changes to allow New Zealand to keep its own authority to make laws with respect to the Maori. In fact, New Zealand was more concerned about racial contamination from Australia than the other way around.
This is not to say that the Maori would not have a worse time of it as part of Australia, but we should be clear that their concerns were not the reason New Zealand stayed out.
The real problem (apart from the Tasman Sea) was the economic and political gulf between the two societies, with New Zealand being much more dependent upon trade with Britain and therefore a potential loser from any Federal laws that changed the existing customs and tariffs regimes was far more important. To get around that you need, firstly, to coopt the New Zealand political elite into the Federation project- tie the two labour movements together, and get big beasts of New Zealand liberalism like John Ballance and Richard Seddon into the Federation movement. Avoid the South African War, at least for a few years- it was hardly decisive, but the contemporary commentator on colonial nationalism, Richard Jebb, was probably on to something when he remarked that the big displays of colonial patriotism and imperial loyalty that overlapped with Federation did a lot to make both societies think about how they were part of the broader empire not a local union. Try and get a bigger market for New Zealand goods outside of Britain- ideally within the rest of Australasia.
It's still a long shot, don't get me wrong, but that could work.
Now, as to your question about the provincial system of New Zealand leading to more states- that's a non-starter. It's an easy mistake to make because 'provinces' sound like a workable sub division, but they were abolished for a good reason- there simply was not enough people for that many governments!
However, separating New Zealand in two is doable.
@Juan Vogel and
@Uhura's Mazda know more about Juan's namessake Julius Vogel than I do, but my instinct is that if there's a way to make him the premier of the South Island (New Munster, probably?) in the 1870s than the two colonies are unlikely to reunify. And if that happens, then two small colonies are more likely to take part in Federation than one. And you only need a single one of them to join, really- because once one of the two islands is its own self-governing colony, than the British government is going to put the same pressure on it that it did Newfoundland to join the local confederation and save London some paperwork.
A North Island state could be interesting if you keep Wellington as its capital, because it would be the only state where the biggest and most important city is not the capital- and in fact where the rural hinterlands and smaller towns are on the capital's side as a balance against Auckland.
A South Island state would probably avoid the long-term decline of Dunedin, which would be one of the only unquestioned Good Things about New Zealand statehood.
So, where does that leave us?
If we assume that these divisions happen, and that most of them happen in the nineteenth century, than our Commonwealth of Australia is likely going to have quite a different constitutional setup. But let's still call it the Commonwealth- it has the states of
Western Australia
South Australia
Victoria
New South Wales
New England
Queensland
Capricornia (Central Queensland)
North Queensland (Mackay? Edwardia?)
Fiji
New Munster (The South Island)
New Zealand/New Ulster (The North Island)
I don't care what anyone says, I didn't forget Tasmania
and the territories of
The Northern Territory
The ACT
and various Pacific Islands in 'association' with the Commonwealth.
*This particular manifestation of scientific racism is a whole
thing, and can be got into another time.