Quick explanation
Redshift is arguably the most important concept in astronomy.
Quite simply, it means that some light, for some reason, acquires a longer wavelength, and that the light hence is shifted toward the red end of the spectrum.
Usually the reason is that the emitter and the receiver are moving away from each other. But in astronomy the reason can also be that the Universe expands, or because the light is emitted from a region of strong gravity.
Motion changes the wavelength of light
When a shining object — e.g. a star or a flashlight — is moving toward us, the wavelength of the light gets shorter and will hence be shifted toward the blue end of the spectrum. Conversely, if the source is moving away from us, the wavelength gets longer, and hence redder.
In the first case the light is said the be blueshifted, in the second it's redshifted. In both cases, the reason is the Doppler effect.
The terms describe the "direction" of the shift; if light if shifted from, say, ultraviolet to blue, or from red to infrared, we still say that it has been redshifted, even though the "final" wavelength is not red.
An analogous effect is met when the sirene from an ambulance approaching us sounds more high-pitched, while it's more low-pitched when it recedes again. For light, however, the cause is fundamentally different, and is described by the theory of relativity.
From lab experiments we know at which wavelengths the different elements emit light. By measuring how much the light from a distant object has been shifted, we can (very accurately) calculate how fast it moves.
The best spectrographs can measure the speed of stars many light-years away with an accuracy of 1 m/s.
The black lines are absorption at specific wavelengths in the stellar atmosferes.
Cosmological redshift
Galaxies are scattered in the Universe, and are actually rather stationary, but because space itself expands, all galaxies recede from each other. When the Universe doubles its size, the distance between two galaxies is doubled. If two galaxies at some moment lie, say, 100 million light-years from each other, after this time has passed they'll be 200 million light-years from each other, while two other galaxies initially lying 200 million light-years from each other end up 400 million light-years from each other
Hence, the farther two galaxies are from each other, the faster they recede from each other. Because the galaxies lie still in space, there is no Doppler shift involved (well, actually they do move around with a few 100 km/s, so there is an additional Doppler shift, but let's ignore that for now). But a prediction of Einstein's general theory of relativity is that space may expand, and that light traveling through an expanding space has its wavelength "stretched", proportionally to the expansion.
Redshift, time, and distance
Because light is redshifted more and more on its way through space, we can use galaxy's redshift as a measure of its distance.
And since light doesn't travel infinitely fast, but took some time to reach us, we look further back in time the farther a galaxy is away. Thus, at the same time a galaxy's redshift is a measure of the age of the Universe at the time we see the galaxy.
That's pretty cool, right?
Gravitational redshift
The third way that light may be redshifted is by gravity itself, causing the light to lose energy. In order to move away from an object ("crawl up the potential well"), the light must move between different reference frames. We can say that it must spend energy to overcome gravity, and when the energy of light decreases, its wavelength increases.
This effect, described by general relativity, is usually much smaller than the Doppler effect. For instance, light from our Sun is redshifted by roughly a millionth, but for small, compact objects such as white dwarves it's some 1/10,000, and for light emitter from the surface of a black hole the redshift is infinitely large, so light loses all its energy and hence doesn't escape.
