“A guy walks into a bar…” is a typical form of what has been called the “bar joke.” One popular joke is:
 
“A three-legged dog walks into a saloon, looks around, and says, ‘I’m looking for the man who shot my paw.’”
 
The joke has been cited in print since at least 1974.
 
 
Google News Archive
27 June 1974, Spartanburg (SC) Herald, “Shaggy Dog Tale” by Don MacLean, pg. A4, col. 7:
It seems there was this dog in the Old West. The dog wore a stetson hat and two guns, one on each hip. One of his legs was in a sling.
 
So the dog goes to the town saloon, kicks open the swinging doors and walks up to the bar. The bartender, quivering at the sight of this fearsome stranger, says, “What do you want?”
 
The dog growls, “I’ll tell you what I want. I want the man who shot my paw!”
 
Google News Archive
16 March 1976, Milwaukee (WI) Sentinel, “Quite obviously, dog was shaggy” by Alex Thien, pt. 1, pg. 9, col. 1:
BILL DURST tells the story about the old dog limping into a western town and walking slowly up the street, past the bank, the hardware store and the sheriff’s office.
 
“Hello, old dog,” said the sheriff.
 
“Hello, sheriff,” said the dog.
 
The dog went on along the street until he got to the saloon. He went in through the swinging doors, limping for all to see, and up to the bar.
 
“Well, old dog, what’ll it be?” said the bartender. “I see you’ve got quite a limp there.”
 
“Sure do,” said the old dog. “I’ll have my regular.”
 
“What brings you to town,” said the bartender, “limping that way?”
 
“I’m here today to find the man who shot my paw,” said the old dog.
 
That’s the worst pun of 1976, barring none, a statement made without reservation or qualification. 
 
20 July 1979, Boston (MA) Herald American, Paul Sullivan column, pg. 24, cols. 2-3:
MIKE HALL, a New York PR man, tells this one:
 
“A little dog, dressed in cowboy clothes ad with a bandaged foot, walked into a bar. It stood on its hind legs, walked the full length of the bar and in perfect John Wayne-style, stopped in front of the bartender, who asked the pooch: “Can I get you anything?”
 
The dog put his bandaged foot on the bar and drawled: “Yup. I’m lookin’ for the man who shot my paw.”
   
majon
Submitted Jokes of ‘95!
From: michael s. kavanagh on Sun Dec 3 07:35:11 PST 1995 :
three legged dog walks into the old wild west saloon and says to the bartender, “i’m lookin’ fer the guy who shot my paw”
 
Google Groups: alt.games.whitewolf
Dark Ages (Nitpicks and spoilers) 
HICKEY MATTHEW
3/10/96
(...)
Werewolf: the Old West?!
“I’m lookin’ for the man who shot my paw.”
 
Google Groups: alt.humor.puns
Animal in Bar jokes?
Nancy Pauline Nadon
2/22/97
(...)
A three legged dog walks into a bar. Goes up to the bartender and says,
“Anybody seen the man who shot my paw?”
 
Google Books
Net-wit.com:
A Smorgasbord of E-mail and Internet Wit Blended with Humorous Incidents from the Author’s Wild and Wooly Life
By Marvin Rubinstein
Rockville, MD: Schreiber Pub.
2000
Pg. 193:
A three-legged dog walks into a saloon in the old West. He sides up to the bar and announces: “I’m looking for the man who shot my paw.”
   
Google Books
A Guy Walks Into A Bar…:
501 Bar Jokes, Stories, Anecdotes, Quips, Quotes, Riddles and Wisecracks
By Michael Lewis
New York, NY: Black Dog & Leventhal Publishers, Inc.
2005
Pg. 75:
A three-legged dog walks into a saloon, looks around, and says, I’m looking for the man who shot my paw.
 
Google Books
Man Walks into a Bar:
Over 6,000 of the Most Hilarious Jokes, Funniest Insults and Gut-Busting One-Liners
By Stephen Arnott and Mike Haskins
Berkeley, CA: Ulysses Press
2007
Pg. 101:
A dog with three legs walks into a Wild West bar and says, “I’m looking for the man who shot my paw.”
 
Google Books
The Quotable Drunkard:
Words of Wit, Wisdom, and Philosophy From the Bottom of the Glass
By Steven Kates
Avon, MA: Adams Media
2011
Pg. 197:
J. D.: A three-legged dog walks into the saloon, walks right up to the bartender and says, “I’m looking for the man who shot my paw.”
Ezra: You might want to work on your repertoire, son.
—THE MAGNIFICENT SEVEN