Originally it came from the jocular 'orl korrect' (all correct), but got wider acceptance during US president Martin Van Buren's 1840 electoral campaign, as the initials of his nickname - Old Kinderhook - were used as a slogan.
It's been used in the UK since at least the early 20th century, but it really took off after WWII.