"sausage on a split roll," c.1890, popularized by cartoonist T.A. Dorgan. It is said to echo a 19c. suspicion (occasionally justified) that sausages contained dog meat. Meaning "someone particularly skilled or excellent" (with overtones of showing off) is from 1896. Connection between the two senses is unclear. Hot dog! as an exclamation of approval was in use by 1906.
