Da gibt es tausend Geschichten, auf die Schnelle zwei davon:
zunächst mal behaupten einige, es leitet sich aus dem englischen "alright" ab, das einfach phonetisch umgetextet wurde.
Die mir plausibelste Geschichte (und auch allgemein akzeptiert) ist:
eine deutsche Frachtfirma namens "Otto Kaiser" pflegte seine Kisten für Übersee besonders gründlich zu packen, zu versiegeln und die Papiere wiese niemals Unregelmäßigkeiten auf. Das wussten auch irgendwann die Beamten in den amerikanischen Häfen. Wenn wieder eine "Otto kaiser"-Lieferung eintraf, schaute man irgendwann die Papiere und Fracht nicht mehr nach. Die Initialen "OK" wurden schließlich zum Synoym für "Alles klar".
Mir ist noch eine eingefallen, eine typisch amerikanische:
Der New Yorker Demokrat Martin van Buren, Spitzname Old Kinderhook (keine Ahnung, was das bedeutet), trat 1840 in einen Wahlkampf. Zu diesem Zweck wirde ein Verein namens "O.K. Democratic Club" gegründet. Die Mitglieder feuerten ihren "Anführer" mit lauten "O.K."-Rufen an. O.K. wurde später zunächst in Karikaturen übernommen und breitete sich so als Zeichen großer Zustimmung aus.