Since it came up last night …
So there’s a ton of info out there on the origin of “Okay” and “O.K.” Most of it is a somewhat overlapping Venn diagrams of similar explanations, sprinkled with folk etymology.
The current consensus is based on research done by A. W. Read in 1963-64:
First, there was an odd cultural movement starting the 1820s of misspelling words as though one were a country hick. This seems to have been either a sign of increasing urbanization leading to urban elites poking fun at their rural cousins, or maybe the opposite, a sense of “common sense” wisdom being a rural phenomenon lost in the crowds of the cities.
An example of this can be found in the aphorisms of “Josh Billings” (Henry Wheeler Shaw), who published entire books in argot like: “Self-made men are most alwus apt tew be a leetle too proud ov the job.”
Think of it as the “I kan haz hamburger?” movement, 150 years earlier.
There was also an abbreviation fad (think LOL, BRB, IANAL, TTFN, ROTFL) in the 1830s, and this extended to creating shortcuts/acronyms for some of these misspelled terms. One of these was taking “orl korrekt” or “oll korrekt” (nobody could agree on how to misspell it) and abbreviating it as “O.K.” (Read traced this back to a Boston newspaper in 1839). Another example was ‘‘K.Y.’’ for ''know yuse" (“no use”); that one didn’t catch on.
In 1840, Martin Van Buren ran for President. He was, in some circles, referred to by his New York home town as a nickname: Old Kinderhook. It was a very small step from there to have one of his political support groups, the Old Kinderhook Club, adapt the extant abbreviation meme, and become the OK Club, which (as other OK Clubs were started around the nation) made the term even better known (even though Van Buren lost that year).
It actually became something of a political football that election, with supporters of Van Buren (calling him the “OK Candidate”) eventually claiming that OK actually derived from “Old Kinderhook,” and his opponents saying that yes it came from “Oll Korrect,” but as the hick spelling used by Van Buren’s predecessor/mentor, Andrew Jackson. As today, making it political meant everyone heard about it, popularizing the term.
From there, we ended up with a word form of the acronym. Woodrow Wilson spelled it out in 1919 “okeh,” because some folk by then were crediting the term as a transference of the Choctaw word “okeh” (see below). By the 1930s, though, the “okay” spelling became more popular and has become universal in the US today.
Now, that’s the consensus. But there are a number of other etymologies that have been suggested over the last couple of centuries of greater or lesser credibility.
- Wolof waw-kay 
- Choctaw hoke or okeh 
- Scottish och aye
- Greek όλα καλά (óla kalá) 
- The OK gesture 
- Haitian French Aux Cayes
- Louisiana French au quai
- Various people with those initials whose sign-offs or stamps of approval featured the letters.
 This page makes a lengthy, passionate, if sometimes overwrought, argument that the term comes from the Wolof / Bantu term waw-kay, or the Mande term o ke. In this argument, the words were brought over with the slave trade, are documented in a few places, but don’t hit the linguistic radar because black slaves didn’t write things down and any spread through the white population carried with it a (slave) slang connotation until the term was “backronymed” into “acceptable” text during that weird abbreviations period. There are points raised in that article that are persuasive enough to make it worth entertaining the possibility, though there’s also a lot of “if you don’t believe this, you’re racist” argumentation. A less adversarial summary shows the hypothesis is at least considered plausible.
 The Choctaw connection was first suggested around 1885, and was the most accepted by linguists and dictionary writers until Read article came out. The Wolof link noted above also has some additional info on the Choctaw connection (which it then dismisses).
Ironically (and bitterly), in 1831, the Choctaw, along with many other Indian tribes, were banished off their lands and force-marched to Oklahoma, which has the state abbreviation “OK”.
It’s worth noting that even Read found the Choctaw connection interesting, and by no means denied it being a possibility.
UPDATE (I had this piece open in another window, and forgot to finish it): This site, provides a lengthy critique of Read, and support of the Choctaw origfin.
 I’ve seen this a few places, but most recently here. If we assume the OK gesture pre-exists the word, then the confluence of a circle and some fingers jutting out can be seen as an “O” and “K” if you squint a lot.
Which leads to the very weird origin of how the OK gesture became (facetiously, then actually) a White Power symbol.
 Which would be really weird, because apparently Greek immigrants to the US who returned to Greece were known as “okay boys” because of having picked up the American term that was, in this argument, originally Greek.
It’s worth noting that people throw around these various origins as if they are all perfect synonyms. They are not, and the fact that “okay” has evolved to have such a blur of meanings (from “perfect” to “meh” to “got it,” from an adjective to a noun (1841) to a verb (1888) to a simple interjection) makes these connections all the more difficult.
Of course, it’s also plausible, if unsatisfying, that multiples of these origins could be true. Memes (which, essentially, words are) sometimes gel from multiple ingredients, all of a sudden, and not all of them are immediately visible. For example “oll korrect” -> “OK” might have become popular beyond some urban wits and newspapers because a phonetically and definitionally similar term was also circulating out there from West African black slaves, reinforced by their contacts (until 1831) with the Choctaw in the southeast, further filtered through whites who used the term. The black slaves and/or Choctaw laid down the tinder, but the white newspapers threw the match.
Not to say that anyone’s had the last word. Only a year after what Read established as the first (surviving) place that “OK” was used, it’s also found in the Lexington Intelligencer (9 Oct 1840):
“Perhaps no two letters have ever been made the initials of as many words as O.K… When first used they were said to mean Out of Kash, (cash;) more recently they have been made to stand for Oll Korrect, Oll Koming, Oll Konfirmed, &c. &c.”
My favorite “OK” story I found.
Although the longer okay may look like the more reputable member of the language, it’s not, as we’ve seen, justified by etymology. It has its supporters, though, with Louisa May Alcott being among the early adopters:
One of us must marry well. Meg didn’t, Jo won’t, Beth can’t yet, so I shall, and make everything okay all round.
— Little Women (1868-9)
As Professor Metcalf notes in an illuminating blog post all about the okay spelling, the 1880 edition of Little Women included neither okay nor OK, opting instead for the word cozy. Um, OK.
The Metcalf article notes this is the only use of “okay” as a word in the entire 19th Century, which may explain why it got edited away.
A few other sources: