The most common explanation is that its origins lie in old directional commands for horses: "gee" (pronounced with a soft /g/ as in genie) to go right, and "haw" to go left. These two utterances are of significant age, and certainly commonplace by the 19th century, since by the time Jack London wrote a short story in 1911, he was using them in reference to commands for sled dogs (search for "haw"). The jump from directional command to general utterance is then not so difficult, especially since the lingo of the American rural west included many slang utterances beginning with y-, like "yippee" and "yo" and "yeah" and "yahoo" (the last of which actually goes back to Jonathan Swift, but was coopted as a fellow y- word).