The joke has been cited in print since 1955. "How do you get to Carnegie Deli?" is a spin-off joke.
Wikipedia: Carnegie Hall
Carnegie Hall (generally pronounced /ˌkɑrnɨɡi ˈhɔːl/) is a concert venue in Midtown Manhattan in New York City located at 881 Seventh Avenue, occupying the east stretch of Seventh Avenue between West 56th Street and West 57th Street, two blocks south of Central Park.
Designed by architect William Burnet Tuthill and built by philanthropist Andrew Carnegie in 1891, it is one of the most famous venues in the United States for classical music and popular music, renowned for its beauty, history and acoustics. Carnegie Hall has its own artistic programming, development, and marketing departments, and presents about 250 performances each season. It is also rented out to performing groups. The hall has not had a resident company since the New York Philharmonic moved to Lincoln Center's Philharmonic Hall in 1962.
Other concert halls that bear Carnegie's name include: 420-seat Carnegie Hall in Lewisburg, West Virginia; 1928-seat Carnegie Music Hall in Pittsburgh, Pennsylvania, on the site of the Carnegie Museum of Natural History and the main branch of the Carnegie Library of Pittsburgh; 1022-seat Carnegie Music Hall annexed to Pittsburgh suburb Homestead's Carnegie library; and 540-seat Carnegie Hall, in Andrew Carnegie's native Dunfermline, Scotland.
Carnegie Hall Joke
A venerable story has become part of the folklore of the hall: A New Yorker (or in some versions Arthur Rubinstein) is approached in the street near Carnegie Hall, and asked, "Pardon me sir, how do I get to Carnegie Hall?" He replies, "Practice, practice, practice." The Directions page of the Carnegie Hall Web site gently alludes to the joke.
1 January 1955, Philadelphia (PA) Tribune, "These Foolish Things" by Jimmy Brown, pg. 12, col. 7:
HAVE YOU HEARD the one about the absent-minded music professor who was rushing to keep a late appointment when a fellow stopped him and asked: "Pardon sir, but how may I get to Carnegie Hall?" Pausing momentarily, the professor said: "Practice constantly."
13 March 1955, Washington (DC) Post, "The Wit Parade" by E. E. Kenyon, pg. AW22:
The absent-minded maestro was racing up New York's Seventh Avenue to a rehearsal, when a stranger stopped him. "Pardon me," he said, "can you tell me how to get to Carnegie Hall?"
"Yes," answered the maestro breathlessly. "Practice!"
9 November 1955, Titusville (PA) Herald, "Try and Stop Me" by Bennett Cerf, pg. 4, col. 2:
Rumor is that a pedestrian in Manhattan stopped Jascha Heifetz and inquired, "Could you tell me how to get to Carnegie Hall?"
"Yes," said Heifetz. "Practice!"
The life of the party:
A new collection of stories and anecdotes
By Bennett Cerf
Garden City, NY: Doubleday
Rumor is that a pedestrian on Fifty-seventh Street, Manhattan, stopped Jascha Heifetz and inquired, "Could you tell me how to get to Carnegie Hall?" "Yes," said Heifetz. "Practice!"
26 April 1957, Washington (DC) Post, pg. B12:
The Journal of the American Medical Association likes the one about the passerby who once stopped Jascha Heifetz on the street and asked: "Can you tell me how to get to Carnegie Hall?"
"Yes," said the violinist. "Practice."
9 December 1960, Lima (OH) News, pg. 22, col. 9:
Tourist in New York City to beatnik:
Tourist—Could you tell me how to get to Carnegie Hall?
Beatnik—Practice, man, practice.
26 March 1961, New York (NY) Times, pg. BR6:
A partial answer to the unfunny situation may be found in the ancient wheeze about the confused traveler who asks a cab driver, "How do you get to Carnegie Hall?" and is wearily told, "Practice, practice."
How about the obvious answer on how to get to Carnegie Hall--walk!
The line is used in the memoirs of a Vienna Philharmonic violinist, Otto Strasser, written in the early 1970s. I don’t have the book in front of me, but I do remember that he tells it using the name of THEIR hall, and the answer is, “Da müssen Sie üben!” The book is “Und dafür wird man noch bezahlt.”