There have been numerous attempts to explain the emergence of this curious colloquial expression which seems to have swept into popular use in the US during the mid-19th century. Most of them are undoubtedly pure speculation. It does not seem at all likely from the linguistic and historical evidence that it derives from the Scots expression och aye the Greek ola kala (it is good), the Choctaw Indian oke or okeh (it is so), the French aux Cayes (from Cayes a port in Haiti with a reputation for good rum) or au quai (to the quay as supposedly used by French-speaking dockers) or the initials of a railway freight agent called Obediah Kelly who is said to have written them on lading documents he had checked.
The oldest written references to OK result from its adoption as a slogan by the Democratic Party during the American Presidential election of 1840. Their candidate, President Martin Van Buren, was nicknamed Old Kinderhook (after his birthplace in New York State) and his supporters formed the OK Club.
This undoubtedly helped to popularize the term (though it did not get President Van Buren re-elected!). During the late 1830s there had been a brief but widespread craze in the US for humorous misspellings and the form orl korrekt which was among them could explain the initials OK. Such a theory has been supported by more than one distinguished American scholar and is given in many dictionaries including Oxford dictionaries.
The only other theory with at least a degree of plausibility is that the term originated among Black slaves of West African origin and represents a word meaning all right, yes indeed in various West African languages. Unfortunately, historical evidence enabling the origin of this expression to be finally and firmly established may be hard to unearth.