Why is a frankfurter in a bun called a hot dog? I have been able to find two explanations, one true and one blatantly false, and as is so often is the case the false one is by far the more interesting. So let's start with that one:
The first person to sell frankfurters in a bun was Harry Stevens, who owned a concession in the early 1900s at New York's Polo Grounds, the home of the New York Giants. T. A. Dorgan, a popular cartoonist on the New York Journal, drew a cartoon about them, in which he depicted them as dachshunds in buns. Since he wasn't sure how to spell frankfurter, he referred to them as hot dogs, and the name caught on.
True but fairly boring
The first recorded use of the phrase is actually in 1895. Yale University students used to refer to wagons selling hot frankfurters in buns as dog wagons and called the sausages 'dogs', probably as a result of conjecture as to the exact nature of the meat used in them (one of the wagons at Yale was actually nicknamed "The Kennel Club"). By 1895 they were known by the now-familiar name of hot dogs. The October 19 issue of the Yale Record contained an article which ended, "They contentedly munched hot dogs during the whole service".
Update, May 1 2003
Tem42 adds, "Recently the story you hear is that Frankfurters were renamed as hot dogs because during WWI it was popular to replace German sounding words with more English sounding ones. Even if that wasn't the true origin on the word, that may be what put it into popular use."