Special relativity deals with inertial frames. A frame of reference, as described by Klaynos, is what we choose to measure things relative to. Someone standing at the side of a railtrack sees a train fly past at 70mph relative to the track, someone sat in that train sees the person at the trackside move past them at 70mph (in the opposite direction) relative to the train.
An inertial frame is one in which Newton's laws hold, that is, a frame which is not accelerating. Try this link for an explination of inertial/noninertial frames with a pretty diagram.
Special relativity states two things:
For any inertial frame the laws of physics are the same - perform an experiment in one inertial frame and you get the same result as in any other inertial frame.
The speed of light, as measured in any inertial frame, will be constant.
Using these, and some geometry, results appear that differ from our common sense notions for adding velocities etc.
