One theory identifies James J. Kilroy, an American shipyard inspector, as the man behind the signature. During World War II he worked at the Bethlehem Steel Shipyard in Quincy, Massachusetts, where he claimed to have used the phrase to mark rivets he had checked. The builders, whose rivets J. J. Kilroy was counting, were paid depending on the number of rivets they put in. They found that they could erase the chalk marks J. J. Kilroy made and get paid double. J.J. Kilroy decided to use a yellow crayon instead; being harder to erase, the cheating stopped. At the time, ships were being sent out before they had been painted; so when sealed areas were opened for maintenance, soldiers found an unexplained name scrawled. Thousands of servicemen may have potentially seen his slogan on the outgoing ships and Kilroy's omnipresence and inscrutability sparked the legend. Afterwards, servicemen could have begun placing the slogan on different places and especially in new captured areas or landings. At some later point, the graffiti (Chad) and slogan (Kilroy was here) must have merged.(Michael Quinion. 3 April 1999.[1])

...

There are many legends attached to the Kilroy graffiti. One states that Hitler himself believed that Kilroy was some kind of American super spy because the graffiti kept turning up in secure Nazi installations, presumably having been actually brought on captured Allied military equipment. Another states that Stalin was the first to enter an outhouse especially built for the leaders at the Potsdam conference. Upon exiting, Stalin asked an aide, "Who is this Kilroy?" Another legend states that a German officer, having seen frequent "Kilroys" posted in different cities, told all of his men that if they happened to come across a "Kilroy" he wanted to question him personally.

The graffiti is supposedly located on various significant and/or difficult-to-reach places such as on the torch of the Statue of Liberty, on the Marco Polo Bridge in China, in huts in Polynesia, on a high girder on the George Washington Bridge in New York, at the peak of Mt. Everest, on the underside of the Arc de Triomphe, scribbled in the dust on the moon, inside a restricted outhouse at the Potsdam conference, in WWII pillboxes scattered around Germany, around the sewers of Paris, and, in tribute to its origin, in the WWII Memorial in Washington D.C.

Really interesting wiki article about a popular WWII Graffiti.