They measure the shift in the star's spectrum. Each element produces a unique "fingerprint" as a pattern of lines in the spectrum. By looking at the position of these lines in the star's spectrum they can tell if they have been shifted from their normal position, this tells them the amount of red shift.
For Instance, if they find the pattern of lines associated with hydrogen closer to the red end of the spectrum than it should be, this tells then that the light has been red shifted. How far it has moved tells them by how much it has been red shifted.