Originally it was short for any of several humorous misspellings of "all correct", including "Oll Korrect", "Orl Korrect", and "Ole Kurreck". This was part of the fads in the 1830s and 1840s of intentionally misspelling common phrases and referring to them by the resulting initials. In the presidential election of 1840, the term "OK" was further popularized by use as an slogan by the O.K. Club, New York boosters of Democratic president Martin Van Buren's 1840 re-election bid; it was an allusion to his nickname Old Kinderhook, from his birthplace Kinderhook, New York. Van Buren lost, but the word stuck. 
This explanation was first documented by Allen Walker Read in several articles in the journal American Speech in 1963 and 1964, and is the only one supported by the earliest evidence. The first recorded use of "OK" was in the Boston Morning Post on March 23, 1839, in the sentence "He...would have the 'contribution box', et ceteras, o.k.--all correct--and cause the corks to fly, like sparks, upward."
There have been many other proposed explanations. There is supposedly a Choctaw word "okeh" that means roughly the same thing, for instance, and Woodrow Wilson, among others, thought this to be the source of "OK". Even after A. W. Read's work, many argue that the case has not been proven decisively, or that perhaps similar-sounding words in other languages did solidify the acceptance of "OK" in American English. Others are skeptical, questioning how many Americans were, say, familiar enough with Choctaw for it to influence their use of English. Another apocryphal account is that the term was used in U.S. military records to state that there were zero casualties or zero killed, hence 0.K., at a particular battle site. The term OK was also used by typesetters and people working in the publishing bussiness. A manuscript that didn't need any changes or corrections would be marked "O.K." for Ohne Korrektur (German for "No changes"). Some say the term Ok comes from the german businessman Otto Kaiser who put his initials on good he had inspected or a Oskar Krause who did quality checks at Ford and marked cars he had inspected with OK. In ancient Greece teachers would mark especially good school papers with "OK" for Ola Kala (everything good). One theory says it comes from a railroad freight agent, Obadiah Kelly, who initialed bills of lading or an Indian chief Old Keokuk who wrote his initials on treaties. Another theory is that it comes from boxes of Orrins-Kendall crackers which were popular with Union troops during the US Civil War. Another theory is that it comes from the brittish English word hoacky (the last load of the harvest). Or the Finnish word Oikea (correct). Or the Scottish expression och aye. Or the French aux Cayes or au quai. Or a word used in many west African languages meaning all right, yes indeed and introduced inthe US via slaves.
From the U.S. it spread to the rest of the world, first appearing in British writing in the 1860s. Spelled out in full in the 20th century, 'okay' has come to be in everyday use among English speakers, and borrowed by non-English speakers. Occasionally it is extended to okey dokey or even, thanks to Ned Flanders, okely dokely.