Hi Tracer: first, it's good when you realize you are confused... This whole cosmology thing IS very confusing...and still confounds me. [If I get something wrong here, somebody please correct it.] After reading this, you may be sorry you asked about velocity in GR!(LOL)
As Dalespam notes, your title and question apply to two different regimes, SR and GR, respectively.
Distant galaxies CAN be moving away from the Earth at speeds GREATER than the speed of light...and so much, but not all, and probably most, of the universe is way beyond our ability to detect via light.
Wikipedia explains further this way:
In expanding space, distance is a dynamical quantity which changes with time. There are several different ways of defining distance in cosmology, known as distance measures, but the most common is comoving distance.
The metric only defines the distance between nearby points. In order to define the distance between arbitrarily distant points, one must specify both the points and a specific curve connecting them. The distance between the points can then be found by finding the length of this connecting curve.
http://en.wikipedia.org/wiki/Metric_expansion_of_space#Measuring_distance_in_a_metric_space
and for a simple illustration of the "curve" :
On the curved surface of the Earth, we can see this effect in long-haul airline flights where the distance between two points is measured based upon a Great circle, and not along the straight line that passes through the Earth. While there is always an effect due to this curvature, at short distances the effect is so small as to be unnoticeable.
from the above source.
Forgetting increasing spatial separation,expansion of the universe, for a few moments, and expanding on the Wikipedia comments:
In SR, flat spacetime, relative velocities at distant points can be compared. Distances are well defined; In GR, curved spacetime, velocity comparisons can only be made at some common measurement point. Distances are NOT well defined because of curvature; There is no global frame of reference in GR.
[This is what Dalespam explained:
SR is invalid whenever curvature is significant
In general relativity, an inertial reference frame is only an approximation that applies in a region that is small enough for the curvature of space to be negligible. So space is curved over larger distances but we keep our observations to only a small region for comparisons. Another way to say this: In curved spacetime there's no globally valid transformation between frames as there is in flat spacetime.
To define a frame (or observer, who has clocks and rulers ) in curved spacetime we must know something about the worldline, the curve (in space and time) along which the frame is carried. This is called parallel transport and different worldlines give different results!
I'll stop here because how all this exactly relates to redshift interpretations has been argued in these forums and I am not confident I understand it.
Expansion: I saved this explanation from Chalnoth and Marcus (whom I trust) :
The simplest way I can think to say it is that you get some very specific total redshift for faraway objects due to the expansion. How much of that redshift is due to the doppler shift and how much is due to the expansion between us and the far away object is completely arbitrary...
the recession velocity is sort of the "obvious" velocity that you would write down: it's simply the Hubble expansion rate times the instantaneous distance to the object (the instantaneous distance is the distance given by the time it would take light rays to traverse the distance if you could instantly freeze the expansion to let those light rays do the bouncing)...
you have a far-away universe emitting light in our direction in the early universe. At the time the light was emitted, the recession velocity of this galaxy was greater than the speed of light, and so as the light moved in our direction, the expansion of our universe carried it away faster than it could approach us.
Redshift vs recession: It's largely just a matter of the description of reality rather than actually being a physical discrepancy. If you so choose, you can select a different coordinate system where the expansion appears to be primarily due to the recession instead of the expansion. The math is just easier in the coordinate system where the expansion is the cause of the redshift.
Marcus: There are several different measures of distance. Recession speed (better called recession rate) is the rate that distance to something is increasing. Before specifying a recession rate one should really say WHICH measure of distance one is using. As Chalnoth pointed out the natural measure when discussing Hubble Law expansion is the instantaneous distance (where you imagine freezing the expansion process at a particular moment so you can measure it, by bouncing a radar signal or however you like, and so measure the distance at that moment). The Hubble Law v = HD is stated in terms of that distance. For the law to apply, D is understood to be the distance "now" (at some moment) and v the current rate that distance is expanding.
I am aware the Hubble constant apparently varies over time...how that affects the above is another issue that confuses me!
However, our universe has an expansion rate (hubble parameter) that is slowing down. So, after some amount of time, after the light ray had traversed some distance, eventually the expansion rate slowed enough that the light ray started to make headway against the expansion, finally reaching us billions of years later. ... So even though the expansion rate slowed enough that the light ray could eventually get to us, it didn't need to slow enough for that galaxy to stop receding at faster than the speed of light...Therefore, there are many galaxies that we can see which always have been and always will be receding at faster than the speed of light.
If anyone can simplify this, BRAVO!