There’s two separate questions that people are answering here. First, is where do these two theories come from. The simpler theory, special relativity, comes from two assumptions: First, the assumption that the laws of physics look the same regardless of how fast you’re moving. In other words, you can’t say absolutely whether something is moving or stopped. There’s nothing new to this; Galileo had a good handle on the situation here. The second assumption, as proved by the M-M experiment and various theoretical considerations (Al didn’t actually know about the M-M experiment until after he published), is that the speed of light is the same as measured by all observers. If you put these two assumptions together and crank through the math (which isn’t actually all that complicated; the most advanced it gets is the Pythagorean Theorem), then you’ll get Special Relativity. For General Relativity, you need the two assumptions of SR, plus the assumption that gravity and acceleration are indistinguishable. In order to make this work, you need some rather …interesting… geometry, so GR isn’t as easy as SR.
The more interesting question, which doesn’t seem to have been addressed well yet, is what these theories mean. In simplest terms, SR states that space and time are related in almost the same way that the different spatial dimensions are related. For instance, you might have a cardboard box that’s 4’ wide, 3’ high, and 12’ long. None of those are absolute, though. If you turn the box around and stand it up, then you now have a box that’s 3’ wide, 12’ high, and 4’ long. On the other hand, if you measure the long diagonal of the box, it’ll always be 13’, no matter how you rotate it. Similarly, the length between two events and the duration between them can change when you “rotate” your reference frame through spacetime, by travelling at a different speed, but there’s something called the spacetime interval (equivalent to the long diagonal of the box) which stays the same no matter what your speed.
Explaining GR is a bit more complicated. Newton said that if there’s no forces acting on an object, then the object will go from point A to point B along the shortest path through space. In GR, what Einstein basically said was that gravity isn’t a force, and that objects travel from point A to point B along the “shortest” path through spacetime. In other words, if you want to get from right here, right now, to the opposite side of the Sun, six months from now, the shortest path through spacetime would be along the Earth’s orbit.
A few other minor points: First, how fast something has to be moving before SR becomes relevant depends on how you define “relevant”. At speeds of .1 c, the answers given by relativity and Newtonian mechanics will differ by about a percent. However, the relativistic effects are always there, and potentially measureable at speeds of a few millimeters a second. Second, physicists nowadays don’t usually talk about the mass of a particle changing; there’s other, cleaner ways to get the desired results out of the equations. Third, when you’re in orbit, you’ve got gravity involved, so you need to use GR. Since GR includes all of the assumptions of SR, the answer you get will already take all of the SR effects into account.