Some believe (including President Woodrow Wilson, who spelled it okeh) that OK comes from an alleged Choctaw word oke, meaning "it is." Others have posited that it comes from French au quai, Scottish English och aye, or some word in Wolof brought over during slavery. All of these theories lack credible documentation to back them up.
Interested in how OK spread throughout the US and the world? There's actually a book* about it.
*I have no affiliation with this book, in fact I haven't even read it (yet). But I saw it on Amazon and wanted to share.