From the Presidential election of 1840. The Democratic candidate, Martin Van Buren, was nicknamed “The Wizard of Kinderhook” — after “Old Kinderhook,” the Hudson Valley village in which he had been born. In reference to this village and Van Buren’s nickname one of the Democratic groups formed to support him in New York City called itself “The Democratic O.K. Club.” Other supporters of Van Buren in New York picked up the term “O.K.” as a sort of slogan, and Democratic rowdies used it as their war cry in their attempts to break up meetings of Whigs. The phrase caught on generally and soon established itself as synonymous with the feeling of the original club members that they and their candidates were “all right.”
Source: Why Do We Say It? The Stories Behind the Words, Expressions and Cliches We Use Castle, Book Sales, Inc. 1985.