If you heard a train whistle from a train moving towards you for the first time in your life, you might think that’s how they always sound. So, when astronomers look at stars’ spectrums, how do they know if it’s really red (or blue) shifted? To recognize such a shift, wouldn’t one have to know what the baseline spectrum looks like? But, how could one know that? 
Each element has a specific pattern of frequencies at which it will absorb and emit. These patterns are easy to recognize even if blue or red shifted (since hydrogen is the most common element in stars by a substantial margin, the hydrogen spectrum (which happens also to be an easy spectrum to calculate) is most often the reference spectrum to determine red/blue shift)
Certain elements emit photons at particular frequencies. The astronomers compared the observed spectrums of the stars against these known values and could then determine whether it is red or blue shifted by the deviation from the known frequencies.
The other answers overlook a key simplification to this question/answer. Red shift increases with distance, so nearby stars exhibit little or no shift, but share the same pattern of absorption lines as distant stars. Thus, red shift detection would be possible even if, for some reason, the hydrogen spectrum had never been observed on Earth.
Just to be clear. Red shift increases with speed (actually that component of velocity moving away from the observer). It just so happens that due to the expansion of the universe, recession speed for those objects outside the local cluster of galaxies is at least approximately proportional to distance. Doppler shifts can also be measured for stars inside the galaxy where distance and recession speed are not very much related at all.
In other words, they’re not just looking at a single line and saying, “Hey, that line is shifted from its normal position.” That wouldn’t be possible, as your question indicates. But there are patterns of lines across the spectrum that indicate, by their width and distance from adjacent ones, a unique signature. If that signature shows up in a star’s light, but the entire signature is shifted toward the end of the spectrum, then whatever emitted that light is moving away from us, causing every wave length to seem longer and appear a little more toward the red end of the spectrum.
In the case of red0-shifting they had a useful yardstick in place to check on distances. It turns out that for a class of variable stars called Cepheid Variables* there is a clear relationship between the period of oscillation of the brightness of the star and its absolute magnitude. But you can also measure the star’s apparent magnitude. From a comparison, you can tell how far away a star is, and that correlates with its velocity (and hence the red shift).
The rule about period correlating with magnitude, by the way, was first checked with stars that had measurable parallax. So we used earlier yardsticks to check newer ones that had the potential to extend things farther. Parallax was used to check Cepheid Variable predictions, which in turn were used to verify red shifts.
Cepheid variables are named after the star delta Cephei, the fourth brightest star in the constellation of Cepheus. Its period was first measured by the teenaged deaf-mute astronomer Joseph Goodricke in the 18th century. Cepheus is the latinized form of Kepheos, the king of Ethiopia 9or Joppa, depending on your source), husband of Cassiopeia and father of Andromeda, who was rescued by Perseus from the sea monster Ketos/Cetus (not the Kraken).
Actually, the red shift of very distant galaxies is NOT a Doppler shift and is NOT caused by their motion relative to Earth.
It’s caused by the metric expansion of space over the course of the trip. As light travels to us from very distant galaxies, space stretches around it, lengthening its wavelength and shifting it toward red.
But you could anticipate the effect if someone had explained the concept of how sound waves work prior to personally experiencing it.
Note too that for any individual star we can observe (as opposed to galaxies containing sagans and sagans of stars), the redshift is going to be very small. So you’d look at a star, and see “Hmm, this looks just like the spectrum of that hydrogen we have in the lab, but with everything shifted .03% towards the red end”. You wouldn’t even notice the redshift unless you knew to look for it.
…Or, you might think “Hey! I discovered a star with a slightly different absorption pattern than a hydrogen star! I’m going to name it faux-hydrogen!” All in all, I believe it is easier to understand the Doppler effect with sound than with light. Perhaps if our eyes saw individual spectra, it might be different, I WAG.
Yes, its easier to understand the doppler effect with sound. For one thing it’s noticeable in everyday life, while things have to move really fast for it to be visible to the naked eye in a spectroscope.
For sound you’d need to know what pitch the source of the sound was supposed to have to measure the doppler shift, but as others have already explained, light from stars have a built in reference.
And your hypothetical scientist might suggest the existence of faux-hydrogen, but next he’d discover that all other elements he could register had the same shift, and that various stars had various shift, but always the same for all elements. Then, after he got busted for speeding by a cop with a laser speed gun, because he was speeding on his way home to tell his spouse about is remarkable discovery, I’m sure he’d figure it out.
I don’t know if I’m reading too much into the OP, but at one point or another, wouldn’t the train pass your position? So you’d hear the whistle for the first time, but as the train passes through your body, the frequency of the sound would drop.
Nitpick: they never actually measured the parallax to any Cepheids, or at least not to the accuracy needed to make the period-luminosity relationship. With ground-based measurements, parallax is accurately measurable out to about 300 ly, and the nearest Cepheid (which happens to be Polaris A, BTW) is further away than that.
Instead, the period-luminosity relationship was discovered by the study of a large group of variable stars that were all about the same distance, i.e. in the Magellanic Clouds. Admittedly, they aren’t exactly the same distance, but they were close enough to formulate the rule.
But they can be used for other things. For instance, they helped (along with other measurements such as proper motion) to determine how the stars are rotating about the center of the galaxy.
Well, since we’re nitpicking here, Polaris used to be a Cepheid, but isn’t any more. Cepheids are one class of stars evolving through a relatively brief phase called the instability strip, and Polaris has evolved back out of that phase since we’ve been observing it. And I’m pretty sure that the original calibration of the Cepheid scale was using Cepheids in the Hyades star cluster, which was in turn measured using a geometric/statistical method called the Moving Cluster Method. There are also calibrations based on using main sequence fitting as a standard candle, and on reverse-parallax on binary Cepheids.
True, the calibration was done that way, but the relationship was first observed among stars in the Magellanic Clouds. By Henrietta Swan Leavitt, who did the work on her own time, since she was not being employed as an astronomer, but rather as a “computer”, at Harvard Observatory at the time.
However, just knowing the relationship did not give the distance to another galaxy. In order to do that, the relationship has to be calibrated. That is, determine the distance to several Cepheids by other means, which was done as you say.