The short answer is: no one knows.
All of Australia’s state flags follow the same basic pattern (the territories are a whole different thing): they are Blue Ensigns, as is the national flag, defaced with a state badge. (Important! “Defaced” in flag-speak means a different thing from “defaced” in regular-speak; just that the flag has been decorated with some other business and not, you know, permanently spoiled.)
So the flag of Tasmania, which was rolled out in 1876, is a Blue Ensign defaced with Tasmania’s state badge: a white disc with a red lion passant (heraldry-speak for “facing left”) in the middle. Why a red lion? Shrug. The Tasmanian government notes that “no official record of the reason for using the lion” exists, though it was probably put there so the early Tasmanian colony could suck up to Blighty. For the record, the lion was originally gold, which at least matches the colour on the United Kingdom’s royal coat of arms.
The flag of New South Wales also has a lion passant, whose origin is vastly less mysterious: perched amid a St George’s Cross (chosen for the state badge because of its British naval associations), the so-called “Lion of the South” is straight-up pinched from the Royal Arms of England. The four stars represent the Southern Cross (which, I didn’t know till I wrote this, is properly known as Crux; that’s Latin for “cross”, don’tchaknow).
Extra fact: the St George’s Cross was supposedly adopted on the NSW coat of arms because, when it was proclaimed in 1906, the then-state premier hailed from the electorate St George (which no longer exists). Heraldry aficionados are such jokesters.
The flag of Victoria was, according to the Victorian state government, the first flag flown by any of the Australian colonies. This is pretty much the most interesting thing about it: it’s pretty much identical to the Australian national flag, minus a big star and plus a St Edward’s Crown. I don’t know why a St Edward’s Crown was specifically chosen, though it’s too common a symbol to be much of exciting mystery.
The flag of Queensland originally had Queen Victoria’s head on it – because it’s not enough to simply name a state after Her Majesty, you have to put her on your flag, too. Anyway, Queenslanders are lazy and it’s super hot up there so everyone decided it was too hard to draw Vicky’s head all the damn time (more or less), so in 1876 she was replaced by a Maltese Cross with a crown in the crux. Why a Maltese Cross? That’s another mystery, though it’s believed that it’s because a Maltese Cross kind of looks like a Victoria Cross. Kind of. But not really.
(Interestingly, a Victoria Cross isn’t quite the shape of a Maltese Cross, but it was supposed to be; it’s one of those mistakes that’s just never been corrected.)
The flag of South Australia carries the state disc: a gold disc with a bird showing off its wings in the middle. The bird, which pops up in dozens of SA emblems, is formally described as “an Australian piping shrike” – which is interesting because there is no such bird. Good one, South Australia! There is some debate over whether the bird is actually supposed to be a common Australian magpie (Gymnorhina tibicen) or a magpie-lark (Grallina cyanoleuca, aka the Murray magpie), though the former seems to be the more popular choice.
The flag of Western Australia is even less creative than Victoria’s: it’s a Blue Ensign with a black swan on it. There are quite a lot of black swans in WA, so it’s not like Sherlock Holmes has to be called in to solve this one. Two notes about the swan: First, it apparently originally faced rampant (to the right), not passant, but was flipped because flag-lovers insist that animals on flags face towards the pole. Second, it looks kind of awesomely creepy close up.
As mentioned earlier, the territory flags follow a whole different pattern from the state flags, though both share the same layout and the Southern Cross.
The blue, white and gold colours of the flag of the Australian Capital Territory were reportedly “chosen for good reasons”. How sensible! To quote: “Blue and white are the livery colours of [Canberra] … while blue and gold … were taken from the national blue and gold appearing on the wreath of the Australian Coat of Arms.” Good reasons indeed. The rest of the flag’s look is lifted from Canberra’s coat of arms (the ACT itself has no coat of arms, FYI): the black swan and the white swan symbolise Australia’s Aboriginal and European people (burn on all the other races, I guess), while you can read what its other features symbolise here.
The flag of the Northern Territory is black, white and ochre, the three official colours of the territory. The flower in the centre, designed by Victorian artist Robert Ingpen, is a stylised Sturt’s desert rose (the territory’s floral emblem) with a seven-pointed star at its centre symbolising the six Australian states and the NT.
And no red mystery lions.