The letters, not to keep you guessing, stand for "oll korrect." They're the result of a fad for comical abbreviations that flourished in the late 1830s and 1840s.
The abbreviation fad began in Boston in the summer of 1838 and spread to New York and New Orleans in 1839. The Boston newspapers began referring satirically to the local swells as OFM, "our first men," and used expressions like NG, "no go," GT, "gone to Texas," and SP, "small potatoes."
Many of the abbreviated expressions were exaggerated misspellings, a stock in trade of the humorists of the day. One predecessor of OK was OW, "oll wright," and there was also KY, "know yuse," KG, "know go," and NS, "nuff said."
Most of these acronyms enjoyed only a brief popularity. But OK was an exception, no doubt because it came in so handy. It first found its way into print in Boston in March of 1839 and soon became widespread among the hipper element.