OK is a quintessentially American term that has spread from English to many other languages. Its origin was the subject of scholarly debate for many years until Allen Walker Read showed that OK is based on a joke of sorts. OK is first recorded in 1839 but was probably in circulation before that date. During the 1830s there was a humoristic fashion in Boston newspapers to reduce a phrase to initials and supply an explanation in parentheses. Sometimes the abbreviations were misspelled to add to the humor. OK was used in March 1839 as an abbreviation for all correct, the joke being that neither the O nor the K was correct. Originally spelled with periods, this term outlived most similar abbreviations owing to its use in President Martin Van Buren's 1840 campaign for reelection. Because he was born in Kinderhook, New York, Van Buren was nicknamed Old Kinderhook, and the abbreviation proved eminently suitable for political slogans.
update: Found a cool link at NPR with a longer story about it. Now I am trying to get myself to always write "all correct" when I would have written "ok". :-)