In 1830s Boston, there was a craze for initialisms, much the same as our current �LOLs', �CUL8Rs' and �IMHOs' in text messages. Thus, they had �KG' for �Know Good' (no good) and �SP' for �small potatoes' (unimportant), for example. �OK' for �Orl Korrekt' (all correct) appeared in the �Boston Morning Post' newspaper in 1839. This is the earliest-recorded version of the new �word'.
The next year, the Democrats started the �OK Club' to support Martin Van Buren, who was standing in the 1840 presidential election. "OK" in this case stood for "Old Kinderhook", which was his nickname, as he'd been born at Kinderhook in New York State. As a result of these two factors, 'OK' and, later, �Okay' became widely popular and are still with us today.
Alternative explanations are sometimes offered - including over a dozen listed below - but there is not a shred of hard evidence to support any of them. They fall under two main headings...language-based and people-based.
A. Language. 1. Scots �Och aye' misheard as �OK'; 2. Greek �olla kalla' (all good); 3. Finnish �oikea' (exact); 4. French �au quai' (at the quay); 5.French �oc' (the equivalent of �oui' in the langue d'oc French dialect); 6. Mandingo (African) �o ke' (certainly); 7 Wolof (African) �waw kay' (yes indeed); 8. Zero killed (battle report).
B. People. 1. �Old Keokuk' (an Indian chief); 2. �Oberst Kommandant' (General Schliessen who fought against British forces in the War of Independence); 3. Obadiah Kelly (well-known freight agent); 4. �Open Key' (telegraphists' jargon); 5. �Ole Korrek' (President Jackson's supposed mis-spelling).
In the end, the �orl korrekt' explanation - as offered by Waterboatman above - is the only one that can be reliably confirmed, so my advice is to go with that and forget all the other etymythology!