Hi, Voyager -
A good place for answers to questions like that is Fuld's The Book of World-Famous Music:

Shave and a Haircut, Bay Rum

Although probably considerably older, this musical phrase is first suggested in print in H. A. Fischler, Hot Scotch Rag
Shave and a Haircut was recorded as a folk melody in 1939 by Rosalind Rosenthal and Herbert Halpert; LC (Music Division—Recording Laboratory, 3646 B4). Unfortunately, the condition of the record does not presently permit verification of the music and words.

Music and words similar to the common music and words appear in the song Shave and a Haircut—Shampoo, published Aug. 3, 1939, by Larry Spier, Inc., 1619 Broadway, New York, N.Y., with music and words by Dan Shapiro, Lester Lee and Milton Berle; JF. The musical phrase also appears in the last three bars of Gee, Officer Krupke in the piano-vocal score of Leonard Bernstein's ,i>West Side Story (1959), p. 178; LC(CDC) and JF (Gee, Officer Krupke, Krup You!).

The musical phrase is also known by other titles and words, and the rhythm alone is frequently tapped or otherwise sounded.

This page (click) has a MIDI and gives an earlier date:

The first recorded occurrence of the tune (with no lyrics) is in an 1899 song by Charles Hale, called "At a Darktown Cakewalk." In 1914, Jimmie Monaco and Joe McCarthy released a song called "Bum-Diddle-De-Um-Bum, That's It!" in which that line was featured in the last two bars of the song. In 1939, the same musical phrase was used in a tune called "Shave and a Haircut - Shampoo" by Dan Shapiro, Lester Lee, and Milton Berle. Somewhere along the line the phrase permutated into "shave and a haircut, bay rum."

When it got to be "two bits" (25 cents) is a mystery. I think haircuts were fifty cents when I got my brushcuts in John the Barber's basement in Detroit in the mid-1950's.
-Joe Offer-