Update: These words were added in September 2017.
Woulda, coulda, and shoulda are not just the constituent parts of a expression you use when you realize that you didn't do something you might've (mighta?) done; they are also words that we are watching (we're not watching mighta, just to be clear). All three words are colloquialisms, and take their initial verb and add a final A as a shortening of the word have. None of them are what would be described as standard English, but, as is so often the case with such words, they have been around for a lot longer than any of the people who might complain about their use.
Given that most of our instances of each are textual representations of spoken language it is difficult to say with any certainty which one actually came first. However, at least as far as print is concerned, coulda has been in use for the longest, by a considerable length of time. The Oxford English Dictionary (OED) provides a citation from 1606 as their earliest recorded use of this word.
....the whole pack of their piperly godheads could a dischargd a stratagem with more spirit of al merit, an ambling nag and a down a down we haue borne her away to dargison.
—John Day, The Ile of Guls, 1606 (OED)But een one hour—een one minute—I could-a conveence you zat I am-a something finer.
—The New York Herald, 9 Jun. 1889
Coulda may be found in occasional use throughout the rest of the 17th and the 18th centuries, and then in the 19th century is joined by the other two members of this phonetic triumvirate. One thing that is striking about the second of the above citations is that many of the words in the example are spelled in order to provide a facsimile of spoken language. This affectation appears to have become more common in the 19th century, as writers used spellings that aimed for the phonetic (often to a ludicrous degree) as a means of indicating the nationality, race, or social or regional status of a speaker. An article from a New Hampshire newspaper in the 1840s, titled The Widow Bedott's Table Talk gives examples of all three of our terms.
I spose you think it curus we should a named our oldest son Hezekier.
Why I've seen him in sitivations when you'd a thought no mortal could a helped grumbling, but he dident.
Most men would a swore, but husband dident. He only said, says he 'Consarn it.'
—The New Hampshire Sentinel (Keene, NH), 9 Dec. 1846
The use of each appears to be geographically widespread, and there is little uniformity of spelling. Apostrophes are placed wherever the writer thinks they will fit, or would best serve a purpose, and so we find should a, should'a, should'a', and many other variants.
"ealth and 'appiness, I wish yer, Mrs. Tarragon,' I say, 'but I should'a thought as Mr. Brockley might 'a chose a younger and a better lookin' woman,' I says!"
—The York Daily (York, PA), 12 May 1875An' de cold an' de damp has gin me de rheumatiz so bad I haint ben able to work much dese yer las' months, an' if it hadn't ben for de goodness of God, I should a starved to death.
—Semi-Weekly Wisconsin (Milwaukee, WI), 7 Nov. 1868"I should 'a whipped 'em like h——l," said McA————n, in relating the circumstance to me.
—Wilmington Daily Dispatch (Wilmington, NC), 12 Jul 1868
In the following examples of woulda, the first is meant to represent the speech of a Dutch man, the second is supposed to be a letter written by a major in the army, and the third comes from a newspaper's rendering of a story in which a child's cat speaks.
"I would'a got it of our toctor to home," said he, "but I was afeard it would leag out zum how or anoder, and den I would be a laughing stog to de whole town."
Easton Gazette (Easton, MD), 24 Mat 1845....he would always say if it had'nt been for his men standin by the cable, and keepin it well greas'd and well matter, as strong as it was, it woulda chaf'd off and that would a ben the last of the "Two Pollies" and Capt. Jumper....
Baltimore Patriot and Mercantile Advertiser (Baltimore, MD), 3 Jul. 1834I arrived at the little grave under the geranium-bush just in time to rescue the lovely wax doll from being buried. 'She's sewed up in a bag,' said Floy, ' and we would'a undigged her.'
—Jamestown Journal (Jamestown, NY), 19 Feb. 1869
What of the expression coulda, shoulda, woulda? This seems to be of much more recent vintage, with little or no written evidence before the 1960s.
Tips are plentiful around a race track, but not all of them are on or about a horse that "woulda, coulda, shoulda" or is "gonna" win.
—Louis Effrat, The New York Times, 17 Dec. 1961Shoulda, coulda, woulda, oughta—but didn't! Call Bruce Caird Realty on these pieces of land before you utter these last words.
—(advt)The Albuquerque Journal (Albuquerque, NM), 12 Aug. 1978Don't be accused of joining "The Shoulda, Coulda, Woulda but didn't Club."
—(advt) News-Press (Fort Myers, FL), 16 Dec. 1972
And in case you were worrying about what order you should place these three words (someone always worries about things like this), there is no set way to do so. You may feel comfortable arranging your shoulda, coulda, and woulda in any way, without regrets.
Words We're Watching talks about words we are increasingly seeing in use but that have not yet met our criteria for entry.