What is "special" and what is "general" in Relativity? Initially I thought in special relativity the velocity was constant, whereas general relativity allowed treatment of accelerated frames as well.
But now I have heard that SR is only valid locally?
 A: In special relativity the laws of physics are covariant under Poincaré transformation, whereas in general relativity the laws of physics are generally covariant, meaning that they take the same form under any smooth co-ordinate transformation. The Lorentz transformations are a special case of general transformations which is why we call them special and general relativity.
A consequence of general covariance and the equivalence principle is that gravity is a feature of curved space-time, so general relativity has gravity while special relativity does not.
There are some people who point out that even special relativity can be written in a generally covariant form. This is true but if we are talking about why we call them special and general that is beside the point because it was only realised later. 
It is certainly not true that special relativity cannot describe accelerations or non-inertial frames. It is just the case that in general relativity these are treated on more equal terms by attributing the difference to gravity.
If we assume that general relativity is the correct theory (as is confirmed by many experiments) then of course special relativity is only an approximation correct locally.
A: The statement that special relativity is valid locally is equivalent to general relativity. This was indeed Einstein's initial logic. He realised that every point in spacetime has a local inertial frame. In other words a falling man feels no gravity - gravity is a fictitious force based entirely on your reference frame!
Originally special relativity was thought to be applicable only to macroscopic inertial frames. If you take special relativity to be valid locally, you expand your symmetries to include all possible coordinate transformations. This generalization leads to general relativity.
A: "The Fabric of the Cosmos-Space, Time, and the Texture of Reality" by Brian Greene is the book which I read first to get introduced with GR and SR. Here is the brief passage to explain the general difference:  

In an empty unchanging universe-no
  stars, no planets, no anything at all-there is no gravity. And without
  gravity, spacetime is not warped-it takes the simple, uncurved shape
  shown in Figure 3.9b-and that means we are back in the simpler setting
  of special relativity. Remember, Einstein ignored gravity while developing
  special special relativity. General relativity made up for this deficiency by
  incorporating gravity, but when the universe is empty and unchanging
  there is no gravity? and so genera1 relativity reduces to special relativity. 



A: 
What is “special” and what is “general” in Relativity?

The "special" in special relativity refers to the fact that it is not a universal theory. Predictions made by special relativity only apply under certain special circumstances. Those special circumstances are where gravitation is not present or can essentially be ignored.

Initially I thought in special relativity the velocity was constant, whereas general relativity allowed treatment of accelerated frames as well.

You'll see a number of places that claim that special relativity only works in (Newtonian) inertial frames. This is not the case, any more than is the claim that Newtonian mechanics only works in (Newtonian) inertial frames. One way to think of special relativity is that it corrects Newton's three laws of motion (but not Newton's law of gravitation) for the fact that the speed of light is finite.

But now I have heard that SR is only valid locally?

Gravitation is undetectable at a sufficiently small scale. Since special relativity rather than Newtonian mechanics provides the "correct" physics when gravitation is not present, one of the key precepts of general relativity is that general relativity must be compatible with special relativity locally. This precept is built-in into general relativity.
"Locally" means has a different meaning to mathematicians and physicists. Physicists care about what can be measured. If you can't measure it, it doesn't exist (at least not until better instruments become available). This means "locally" depends on how much mass-energy is nearby and on how good ones instrumentation is. "Locally" in the vicinity of a black hole is a rather small region of space-time. "Locally" is a rather large region in the middle of a billion light year diameter void in space.
A: SR: Flat Space-time (Minkowski metric), no gravity, Lorentz coordinates transformations (usually $\Lambda \in SO^+(3,1)$, the proper orthochronous Lorentz group). Acceleration is allowed, but you usually want to work with inertial frames. 
GR: Curved Space-time (non trivial and dynamic metric tensor), theory of gravitation, generic coordinates transformations (usually $\Lambda \in GL(4)$, but more in general $\Lambda \in Diff(M)$, the diffeomorphism group of the Manifold). The equivalence of gravity and acceleration is manifest. You can always find a local inertial frame that is flat, and in this frame you recover SR.
A: Special relativity is physics in a $3+1$ dimensional Lorentzian spacetime, with the additional requirement that the spacetime is flat, which determines spacetime completely.
General relativity is physics in a $3+1$ dimensional Lorentzian spacetime, with no additional geometric requirement. An equation for the metric is required to determine the spacetime, this equation is the Einstein field equation.
The thing that is more general about general relativity is not the coordinates you can use, not the frames you can use, but it is the geometry of spacetime. Coordinates and frames are not physical, so you can't find more physics in a theory by allowing more general coordinates and frames. But by letting the geometry be a dynamical object, we find a lot of new physics.
A: Basically general relativity is the theory of gravity. However things from special relativity can be solved by general relativity. Special relativity is the framework for general relativity. Special relativity is valid locally for the most part. However sometimes it is just more accurate to use special relativity locally.
A: SR can be seen as a special case of GR, where you have a fixed (i.e. non dynamical) and flat spacetime: this  is drastic, as you boil down the full Einstein equations to just conservation of the stress energy tensor.
Another possibility is to see SR as the local approximation to GR (only if you expand the metric locally to the second order you see GR effects: the spacetime of GR is a manifold that is locally flat).
In my opinion the best way to appreciate how SR is embedded into GR is to go for the "tetrad formalism": loosely speaking, SR is the theory on the local tangent space.
Note that I am not mentioning inertial frames, acceleration, coordinates, gravity etc.. just take GR, with its full machinery, impose a fixed flat spacetime (use the coordinates you want, but it must be flat), and you have SR: from this point if view it is clear why SR is "special".
