This a perennially confusing question which I attempted to answer on Quora (http://www.quora.com/What-does-the-constancy-of-the-speed-of-light-is-deduced-from-the-principle-of-relativity-mean-exactly). I also wrote a whole book, "Relativity Made Real", to provide a more detailed answer. Contrary to popular expositions, there is no really short and meaningful answer to this question, but here was my effort on Quora to condense the issue (and my book!) to its essence:
Special relativity is best divided into two conceptual pieces. The first, and most important, is a qualitative observation that all objects must be affected by motion. This is really not very surprising when one considers the structure of matter, i.e., electrons and nuclei held together by electric forces. The electric forces take time to transmit between the particles, so when the object is set into motion then obviously there are some very complex changes to the forces inside the matter. It would be remarkable indeed if its shape and size did not change, along with the rate of any processes it happens to be experiencing (e.g., ticking, if it is a clock).
A good analogy is to imagine the individual electrons and nuclei as tiny people holding megaphones. They try to arrange themselves in a nice crystalline structure by shouting back and forth at their neighbors through the megaphones, and estimating their distances based on the response times and the volumes of the voices. The sound waves they exchange are analogous to the electric field, which also is transmitted by a type of wave, namely electromagnetic waves.
If we now set this "object" made from tiny people into motion, it will be thrown into disarray, because now the sound waves will take more or less time getting from one person to the next, the voice volumes will be changed, and all the calculations will be off. The collection of people will not be able to maintain the same shape, and likewise a collection of moving atoms cannot maintain its same shape.
But if all objects are physically changed by motion, then so are measuring devices like clocks and rulers, which immediately implies that moving observers will also measure different values for almost every quantity. There is nothing sacred about measurements; they are carried out by ordinary physical objects, and the results they produce are dictated not by prior principles or philosophy, but by the physical system they are embedded in.
The situation we just described could clearly become extremely complicated, with arbitrarily complicated motion effects. It is indeed very easy to write down arbitrarily complicated laws of this kind, and we wouldn't (and probably couldn't) live in such a universe. Here is where the second piece of the relativity puzzle comes into play: the "principle of relativity" postulates that our actual laws come from a subset of this larger, possible set, a subset which has a very special property.
When one studies the effect of motion on objects which are "held together by waves", as described above, one finds that there is a very surprising mathematical possibility for their behavior. The various waves involved can be structured in such a way that the effects on moving objects are exactly calibrated so that all observers will always measure the same speed for the waves ("speed of light"). It is extremely non-obvious that this is possible, and it certainly is not necessary in any way; our universe could have been built otherwise. (And it could also have been built without any waves at all, in which case Einstein's relativity would be impossible, and we would be discussing only the relativity of Newton/Galileo).
This "principle of relativity" essentially postulates that our universe has the simplest kind of laws it can have, given that it is built on a foundation of waves. It places great restrictions on the allowed wave laws, to the point that many effects can be computed without even knowing anything else about those laws. That is why the "principle of relativity" appears to function as a free-standing law on its own, even though it is really a property of the underlying quantum wave laws of physics (for example, one can write down the Standard Model of particle physics without ever saying the word "relativity").
So the principle of relativity does, indeed, imply that everyone measures the same speed for light; in fact, that is the entire content of the principle. But under the hood what it is doing is picking out a certain very special subset of the enormous collection of possible wave theories, and postulating, rather hopefully, that our universe is described by only these kinds of wave. It certainly didn't have to be that way, but if it wasn't then it would be so complex that living creatures would probably never have evolved to discuss it.