From Mother Tongue - English & How It Got That Way by Bill Bryson:

Of all the new words to issue from the New World, the quintessential Americanism without any doubt was O.K. Arguably America's single greatest gift to international discourse, O.K. is the most grammatically versatile of words, able to serve as an adjective ("Lunch was O.K."), verb ("Can you O.K. this for me?"), noun ("I need your O. K. on this"), interjection ("0. K., I hear you"), and adverb “We did O.K."). It can carry shades of meaning that range from casual assent ("Shall we go?" "O.K."), to great enthusiasm ("O.K.!"), to lukewarm endorsement ("The party was O.K."), to a more or less meaningless filler of space ("O.K., can I have your attention please?").

It is a curious fact that the most successful and widespread of all English words, naturalized as an affirmation into almost every language in the world, from Serbo-Croatian to Tagalog, is one that has no correct agreed spelling (it can be O.K., OK, or okay) and one whose origins are so obscure that it has been a matter of heated dispute almost since it first appeared. The many theories break down into three main camps:

1. It comes from someone's or something's initials - a Sac Indian chief called Old Keokuk, or a shipping agent named Obadiah Kelly, or from President Martin Van Buren's nickname, Old Kinderhook, or from Orrins-Kendall crackers, which were popular in the nineteenth century. In each of these theories the initials were stamped or scribbled on documents or crates and gradually came to be synonymous with quality or reliability.

2. It is adapted from some foreign or English dialect word or place name, such as the Finnish oikea, the Haitain Aux Cayes (the source of a particularly prized brand of rum), or the Choctaw okeh. President Woodrow Wilson apparently so liked the Choctaw theory that he insisted on spelling the word okeh.

3. It is a contraction of the expression "oll korrect," often said to be the spelling used by the semiliterate seventh President, Andrew Jackson.

This third theory, seemingly the most implausible, is in fact very possibly the correct one-though without involving Andrew Jackson and with a bit of theory one thrown in for good measure.

According to Allen Walker Read of Columbia University, who spent years tracking down the derivation of O.K., a fashion developed among young wits of Boston and New York in 1838 of writing abbreviations based on intentional illiteracies. They thought it highly comical to write O.W. for "oll wright," O.K. for "oll korrect," K. Y. for "know yuse," and so on. O.K. first appeared in print on March 23, 1839, in the Boston Morning Post. Had that been it, the expression would no doubt have died an early death, but coincidentally in 1840 Martin Van Buren, known as Old Kinderhook from his hometown in upstate New York, was running for reelection as president, and an organization founded to help his campaign was given the name the Democratic O.K. Club. O.K. became a rallying cry throughout the campaign and with great haste established itself as a word throughout the country. This may have been small comfort to Van Buren, who lost the election to William Henry Harrison, who had the no-less-snappy slogan "Tippecanoe and Tyler Too."