The following is a revision of a post originally published in 2005. But now it has pictures!
I heard a talk radio commentator talking about tonight’s speech from President Bush. (Update: In fact, it was the newly (maybe) elected senator from Minnesota, Al Franken, on his now canceled Air America program.) At one point he said,
…previous State of the Unions, er, States of the Union, uh, previous State of the Union addresses!

With the full phrase, making a plural is no problem.
Franken took the easy way out: He couldn’t decide whether to pluralize state or union, so he resorted to using the full phrase State of the Union address, and pluralized address.
His cohost, however, confidently and repeatedly talked about previous “States of the Union,” undoubtedly patting herself on the back the same way she does when she says mothers-in-law, passersby, and teaspoonsful instead of mother-in-laws, passerbys, and teaspoonfuls. But in fact, Franken had it right the first time, with State of the Unions.
It’s not a matter of correctly identifying the head noun in a noun phrase, as with mother-in-law or son of a bitch. These phrases are different from State of the Union because they’re generally used as nouns. Although state of the union can be used as a noun (as in, “He shall from time to time give to the Congress Information of the State of the Union”), in the phrase State of the Union address, the four words have essentially been boxed up to serve as an adjective. (In the diagrams, it’s labeled Nom, for “nominal”, for reasons that are more fully explained in this post from Arnold Zwicky.) When you shorten State of the Union address to just State of the Union, you don’t have to worry about opening up the box to figure out where to put your plural affix; you just stick it on the edge of the box just like you do any other time you’re using an adjective to stand in for an adjective-noun collocation: The greens make you horny; the crazies are out tonight; the movies in this bin are the two-fer-ones; put all the one-of-a-kinds here. (Exceptions: the young, the rich, the dead, etc.)
In fact, if you hyper-correctly say “States of the Union,” then you shouldn’t be talking about speeches at all, but actual states that the union has found itself in. Or subsets of the 50 states that make up the USA, which in fact is what the phrase is usually used to refer to. Online, the only place I’ve found it referring to State of the Union addresses is here:
George W. Bush: Translated States of the Union (link)
State of the Unions is out there, in quotations like the two below, but mostly it shows up in titles of articles about labor unions, or sometimes civil unions, where the -s does indeed attach only to union.
Even Bill Clinton, a president with very different views to those of Reagan, famously said in one of his state of the unions, “the era of big government is over … (link)
No other president since Franklin Roosevelt took office in 1933 has mentioned God so often in his inaugurations or State of the Unions. (link)

The problem comes when you leave out address...
So State of the Unions should have been perfectly OK, but unfortunately it sounds like a son-of-a-bitches kind of mistake. Not to mention that it’s ambiguous, since you can’t tell just by hearing it whether the -s is attaching to the entire string state-of-the-union, as in the diagram on the left, or just to union, as in the diagram on the right. In order to avoid the ambiguity, I’d have to say Franken’s final answer, State of the Union addresses, was the right way to go. But in the context of the utterance, State of the Unions wouldn’t have been ambiguous in practice, and it’s certainly better than States of the Union, neither of whose compositional meanings are the intended one.

...because it could be mistaken for this.

:

:

:

:

:

:

:

:

:

:

:

: