Red shifted to what? I searched and found a lot of questions and answers about red shift here but none with the answer to mine. (sorry if it is there somewhere and I did not find it.)
Everyone is saying the light from the far away galaxies is red shifted and I could find a lot of formulas and physics theories about that.
My question is: light is red shifted compared with what? Why is not possible for the source to emit red light? I'm asking this question keeping in mind that first they saw red light and then decided that the Universe expands not the other way around.
 A: A complementary answer to Chris's, the middle row is the spectrum at rest.


A blue shift does not mean that the object ends up blue. It just means that the entire spectrum is shifted up in frequency. Note that this is a schematic diagram and not actual data.



When a star emits light, the color of its light as observed on earth depends on its motion relative to earth. If a star is moving towards the earth, its light is shifted to higher frequencies on the color spectrum (towards the green/blue/violet/ultraviolet/x-ray/gamma-ray end of the spectrum). A higher frequency shift is called a "blue shift". The faster a star moves towards the earth, the more its light is shifted to higher frequencies. In contrast, if a star is moving away from the earth, its light is shifted to lower frequencies on the color spectrum (towards the orange/red/infrared/microwave/radio end of the spectrum). A lower frequency shift is called a "red shift".

See this link also 
It is the fixed locations of the absorption lines in the spectrum that allow identifying the element absorbing those lines. Just a shift overlaps them.
A: The other answers (as of this posting) stick mainly to "light"... but the same concepts exist in other forms of "waves"
Red/Blue Shifts and associated "Doppler effects"
I want to add associated ideas that you can, literally, hear: Sirens and Train Horns.
The basic idea of "shifts" is that the waves that you see, hear, experience change based on how they are generated in relation to you.
Something looks/sounds/feels different if it's coming towards you... vs when it's going away from  you. That's because you experience shorter or longer "waves"
https://www.space.com/25732-redshift-blueshift.html

Redshift and blueshift describe how light shifts toward shorter or
  longer wavelengths as objects in space (such as stars or galaxies)
  move closer or farther away from us. The concept is key to charting
  the universe's expansion.
Visible light is a spectrum of colors, which is clear to anyone who
  has looked at a rainbow. When an object moves away from us, the light
  is shifted to the red end of the spectrum, as its wavelengths get
  longer. If an object moves closer, the light moves to the blue end of
  the spectrum, as its wavelengths get shorter.
To think of this more clearly, the European Space Agency suggests,
  imagine yourself listening to a police siren as the car rushes by you
  on the road.
"Everyone has heard the increased pitch of an approaching police siren
  and the sharp decrease in pitch as the siren passes by and recedes.
  The effect arises because the sound waves arrive at the listener's ear
  closer together as the source approaches, and further apart as it
  recedes," ESA wrote.

The "red/blue shifts" are the same basic effects experienced when you hear a difference in something coming towards you vs going away. That change is perceptible - and measurable - and the expected "wave" vs detected "wave" is valuable information.
A: There are certain physical processes that always produce a light of the same wavelength. For instance, hydrogen changing from the $n=2$ to the ground state always emits a photon with an energy of $10.2~\rm eV$, corresponding to light with a wavelength of $122~\rm nm$.
There are many processes like this, which form "spectral lines" that should be the same everywhere in the universe. So if we see a stellar object with the same spectral lines, just all shifted over by the same amount, we can reasonably determine that the light is redshifted.
A: Redshifts doesn't actually mean the light is red, or was ever red. That's what is confusing you.
"Red" and "blue" in this context are shorthand ways to say "towards longer wavelengths/lower energies" (red) and "towards shorter wavelengths/higher energies" (blue), because in the visible light spectrum, red is at the low energy end of what we can see, and blue at the high energy end. In simple terms,  light, radio, gamma waves - any electromagnetic radiation at all - from a source that is "red shifted" is a way to say that it is received  (by us) at a lower energy than it "really" was emitted (assuming a suitable reference frame).
But it could be any radiation at all. So "redshifted" could describe:


*

*gamma rays emitted from a distant galaxy that we detect as x rays,

*yellowish/white visible light from a star like our sun that an extragalactic observer detects as visible but more orange tinted due to their velocity,

*ultraviolet light perceived as blue visible light

*infrared rays perceived as radio waves


so long as the explanation is based on the relative velocity of the emitter and observer, the effect of gravity, or the expansion of space (which actually "stretch" or "compress" the wavelength of each photon), and not due to factors such as filtering of light, which just bias the photons received.
The same kind of statements, but inverted, are true for blue shifted light (orange light seen as yellow/white, xrays received as gamma rays, etc)
Importance
Many kinds of light we see in the universe are very well defined. For example, we know exactly what frequencies of light, excited hydrogen  can emit when it loses energy. We also know exactly what frequencies hydrogen gas clouds can absorb as light travels through them (so that specific frequency is "missing" when we see it). [They're the same thing!]
The frequencies related to each source commonly show up as a pattern of very specific frequencies, or a distribution of frequencies, not just one frequency. These patterns of frequencies are different for each element and act like a "fingerprint". In simple terms, it's possible to look at a pattern of frequencies (often drawn as "spectral lines" in graphical form), and be sure which lines represent what element. It is so specific, that we can often even identify the exact interaction that gave rise to the radiation (specific interactions usually have well known energies for the photons they  produce). Knowing this, we can be sure what the original frequencies for that interaction or element would "really" have been. The difference between that and the frequency we actually detected, is the red or blue shift that the radiation has experienced.
So a cosmologist can tell from the spectra they detect, what original frequencies were emitted, and they can also be absolutely sure whether the light or radio or other waves they detect always were that frequency, or were originally  emitted at a different frequency but has been red or blue shifted by some amount (=received at a lower or higher frequency), and that this is due to their high relative velocities.
(The other possible cause is gravitational redshift, see next section)
Causes
In astronomical terms, the most common cause by far for red/blueshifting is an object's relative velocity towards or away from Earth. In this case, the red/blueshift is ultimately due to special relativity (the movement of objects relative to an observer in spacetime). Whether in our own galaxy or elsewhere, most objects in space are moving towards or away from us. On a cosmic scale the expansion of the universe means that almost everything outside our own galactic supercluster is moving away from us at high speed - and the further away the faster it's received. Light and other radiation received from very old objects, which has been travelling for billions of years, will also be redshifted, because that radiation will have been affected by the expansion of space over time, so on a very large cosmic scale, redshifting is linked to time/age/years ago  and distance, as well as velocity - known as Hubble's Law. Whether the velocity is due to space expanding, or the object's own movement within space, a red/blueshift will result.
The other known cause for redshifting is the effect of extreme gravity, known as "gravitational redshift". In this case, the ultimate explanation is general relativity (the effect of mass and gravity on spacetime). For example, radiation given off very close to a massive object such as a black hole, or perhaps passing a very massive object on its journey to us, could be redshifted due to gravity. (Theoretically it could work the other way around as well - an observer who could somehow hover right in the vicinity of a black hole might see other objects as blueshifted - but in practice this is a perspective we never see on earth.)
Historically for a time, this "dual cause" led to some confusion, because in the early days of radio astronomy, astronomers weren't always sure if they were seeing a very distant/fast-moving object, or a nearby object affected by gravity. However, these days astronomers are usually very sure which they're looking at.
Example
Suppose we try and use this knowledge. Instead of saying just that we detect radio waves of some frequencies from a source, we can say (for example) that what we detect is a match for emissions from hydrogen, with some carbon, and that the hydrogen lines were redshifted by X amount but the carbon spectrum was blueshifted by Y amount. Therefore we conclude we're actually looking at 2 objects, probably one containing carbon that's traveling towards us at a certain velocity, one containing hydrogen travelling away from us at a certain velocity. Perhaps one source is almost behind the other, or it's a binary star system. From the velocities and amount of red/blue shift, we can decide the distances (are either source in our local galaxy or cluster, or are they billions of light years away), and much more. 
If they are in a binary system we can expect to see their red/blueshifts change periodically as each of them moves more towards us, then more away. From their emissions we can figure what type of stars they are and therefore their likely/estimated mass (I'm simplifying a lot!). From the time taken to rise and fall in red/blue shift we can work out how long they take to orbit, and their relative masses, distances apart, etc. And so on, and so on.
As a (simplified!) second example, we can measure the spectra of stars at the centre of our galaxy. If we plot over time, the star's positions versus the amount of red or blue shifting of their light, we find they periodically undergo changes in shift - redder shifted, then bluer shifted. That says their velocity relative to us gets larger and smaller. Conclusion: the stars in the centre of our galaxy are all orbiting something. The amount of shift and distance, and a bit of computer work, lets us work out how "tight" all their orbits are. So we can work out the mass of whatever they are all orbiting. We can discover the object has a huge mass. But we also know the size of the smallest orbits of these stars. Whatever the object is, that they're orbiting, it has to be smaller than the orbit of the stars, otherwise the stars would quickly lose energy and spiral in/merge. When you point a telescope there, you don't see any giant mass object - but we know one is there.  It turns out that to fit that amount of mass in that size space, you'd have to have a black hole. Nothing else would do it. And that's one way we can be certain there's a large black hole at the centre of our galaxy (and many others), and calculate its mass. All from stellar red/blueshift measurements!
Update: Hubble's law of redshifted light and the expansion of the universe
Coming back to the OP, the question specifically refers to redshifted light and "deciding the universe was expanding". So I'll try a quick explanation (this is a whole question of its own!). 
About a hundred years ago, Hubble formulated his law (more accurately a rule of thumb) which said that light from distant galaxies was redshifted, and the more distant the galaxy, the more redshifted the light. Where galaxies were close enough to be measured directly, they turned out to be receding from Earth. 
Now, this might have meant they were all travelling outward at extreme velocities from some common centre, but could have many other meanings: one theory suggested matter was being created continually to replace it (the rate would have been very small). 
So although the Big Bang was conceptualised, there actually wasn't much evidence and it was only several decades later that other overwhelming evidence (radio astronomy, standard model, cosmological modelling, stellar lifetime cycles, expansion of space, fusion processes, and myriad other discoveries) gradually ended up supporting the Big Bang theory. 
We are now extremely sure, from many different kinds of observation and knowledge, that light from distant galaxies is redshifted to lower frequencies because of the expansion of space, and the Cosmic Microwave Background can be detected and identified as an extremely redshifted form of light from excited hydrogen atoms emitted at the dawn of our universe, when it was about 370,000 years old. 
But it's important to remember that it was not immediately obvious or accepted by many astronomers for several decades, that redshifted light meant that our known universe had to be expanding, or began at a specific point in time. People didn't just jump at that conclusion. They had extreme redshifts, that was undeniable - but what did they mean?  It was not even clear how a universe might expand, if it did, or what might lead to an expansion, if that was what was being seen. So there were many unsatisfactory questions and doubts. As with much of science, the actual observations came first. Gaining an understanding of them, and what they meant, and testing theories which might explain a universe with those observations, took many years after that time.
However, once modern cosmological ideas of the Big Bang began to be taken seriously as a theory, the detailed evidence gained through redshifted radiation became crucial evidence for both of these ideas and for much of modern cosmology.
