According to William and Mary Morris's 1967 Dictionary of Word and Phrases, the decidedly dorky colloquilism "hunky-dory" is probably rooted in the slang used at a Dutch settlement in New Amsterdam where hunk was close to the Dutch word honk, meaning goal.
However, the following story behind the term "everything's hunky dory" is decidedly more entertaining, even if it probably isn't actually true. In Yokahama, Kapan, the principal street that sailor's on shore leave kept an eye for to keep from getting lost was called Hunchodori Street. So long as sailor wandering around knew where to find Hunchodori Street, he knew he could find his way back to the ship.
A similar version of this history of "hunky dory" is that the term honcho-dori means the equivalent of main street for towns that have one. U.S. Sailors may have developed the habit of asking for directions using a bastardization of the word when in any number of cities.
The term has been in use in the english language since the middle of the 19th Century.