So you're somewhere—on vacation, at war, time traveling, teleporter accident, whatever—and you want something that'll stick around longer than just a Fun T-Shirt. That's easy, just vandalize a handy surfacenote vandalism is illegal in most places, so Don't Try This at Home (or anywhere else, really)!
This trope is pretty much as old as humanity itself (it's posited that there are hand-prints at Lascaux for this very reason, among other theories), but the Trope Namer is a bit of Memetic Mutation from World War II whose origin has many stories (see Real Life section below).
Do not confuse with the Styx album.
City Hunter: Ryo, who enjoys mocking his adversaries and pulling pranks on them, is quite fond of playing this trope when he infiltrates into his enemies' lairs. Before leaving, he vandalizes pictures, writes insults on the walls -or comments about their enemies' penis size-, paints drawings of them... He makes this because an angry enemy is prone to commit mistakes... but mostly because he gets a good laugh out of pissing them off.
Pokémon: The memetically infamous "Gary was here! Ash is a loser!"
In one Footrot Flats strip, Wal makes a moving speech about how insignificant it makes one feel knowing that an ancient tree will still be standing centuries after he's dead. He then carves "Wal Footrot Was Here" into the trunk.
Journey to the West: Sun Wukong makes a bet with the Buddha that he can leap out of Buddah's grasp. He goes an extreme distance away and finds a set of pillars. Thinking that he'd won, he leaves the words "Son Wukong Was Here" on the middle pillar and urinates on it for good measure. Turns out the "pillars" were Buddha's fingers. Oops!
In The Neverending Story, there is a mountain that is only conquered for the first time - that is, you are always "the first person to ever climb it"; it is impossible to get on the top as long as there is any memory of anyone doing it before. So leaving a tag at the top blocks everyone else from it until the tag is worn out by the elements.
In The Shawshank Redemption, inmate Brooks, unable to fit into society after so many years in prison, carves "Brooks was here" into a ceiling beam from which he then hangs himself. At the end of the film, Red carves "So was Red" before leaving to join Andy in Mexico.
Isaac Asimov's short story The Message is about a time traveler from the 30th century to WWII North Africa who, forbidden to interfere (he can only observe) resorts to writing a message on the wall of the hut he was in. His name is George Kilroy.
In My Name Is Earl, Randy had made several graffiti like this, and after the episode where he goes back to school, he sets Earl to correct them since he [Randy] has realised that those graffiti had bad spelling.
Two Kilroy faces appear in the opening credits of Community, with the noses forming the l's in "Joel McHale".
In the radio program The Black Museum (based on real cases of Scotland Yard and real objects in their 'Black Museum'), episode 'The Notes', police find notes actually saying 'Kilroy Was Here." The police eventually realize the killer is actually telling them his name is Kilroy!
The OGL d20 Modern setting "Weird Wars" uses "Kilroy" as a kind of spirit that has allied itself with the Allies. It possesses random soldiers and leads them to perform suicidally effective charges against Axis positions. When its host is killed, it discorporates, always leaving the graffiti "Kilroy woz 'ere" imprinted on a nearby surface.
As mentioned above, "Kilroy was here". However it originated (The Other Wiki has a few theories), American soldiers began leaving Kilroy everywhere.
Graffiti tags. There's even a "language" associated with specific artists and gangs depending on what elements are present in a tag.
Places like Names Hill, Register Cliff, and Independence Rock in Wyoming; according to Wikipedia, people on the Oregon Trail and the like carved or had carved their names in them. Names Hill also has Native American pictographs.
One Viking trader scratched this tag in his native language into the wall of what used to be a church in Constantinople.
During the Potsdam Conference Harry Truman allegedly had some fun at Joseph Stalin's expense by sneaking into his private bathroom and writing this on the wall. Stalin, in characteristic fashion, had the KGB on high alert looking for this mysterious "Kilroy".
In general, any video game that lets you leave behind some kind of message (text or graphical) can result in this trope.
This, and bragging rights, is the whole point of high score lists.
Left 4 Dead has graffiti in every safe house as a form of pseudo-communication between groups of survivors. Among them is Chicago Ted, whose statistics for zombie killing become something of a legend.
In Pokémon Ruby and Sapphire, outside Lilycove City's Pokémon Fan Club building, it is noted that a number of Trainers have scribbled their names all over its sign. There is also a small island in the waters by Seaside Cycling Road that Team Aqua (or Magma) have tagged ("Team Aqua Was Here!").
In EarthBound, checking a certain sign in Summers shows a message from Porky insulting Ness.
In the Looney Tunes short "Haredevil Hare", Bugs Bunny lands on the moon (in 1948) and mentions that he's the first living creature to do so. He then passes a rock with "Kilroy was here" written on it.
The Simpsons: In earlier seasons, "El Barto" graffiti tags can be seen all over town. Unsurprisingly, the cops never suspect Bart as the culprit.
In another episode, Bart writes his name in wet concrete, with an Imagine Spot of the future, where archeologists speculate on what he might be like.