I think it's one of those mathematically true statements that is also annoyingly misleading. Here is my own explanation:
I'll stick to Special Relativity, "SR", but the arguments below can be extended to General Relativity.
What separates SR from Newton's mechanics most clearly is what is treated as "invariant under transformation". Relativity exists in Classical mechanics too, but with a different transformation. In this world the invariants are time and length separately -- where length is calculated using Pythagoras' Theorem.
In SR, these two are combined of course, so that time and length are together invariant in the "four-length" s, with s^2 = (speed of light * time)^2 - length^2, or:
s^2 = (ct)^2 - L^2
Now this length s has units of distance, and is also invariant under the transformation laws of SR, which are the Lorentz transformations. What is important is that once you have measured s for any particular situation, it takes that same value no matter how fast you are moving. In particular, if you are moving at a speed such that the length measured (or strictly the change in length) is zero, then we have that:
s = ct => (s/t)^2 = c^2
This horrible abuse of notation is nevertheless correct in essentials (just change the notation to the correct one and be a bit more careful by what you mean by "time") and tells us that we can define something called "four-velocity" which is:
u = s/t with u^2 = c^2 = constant.
This value is also constant under transformations, so that all objects have a 4-velocity equal to the speed of light in spacetime.
There are two reasons I think this is misleading, though. Firstly, if you start defining this 4-velocity to be the only one that matters then a similar argument would lead to the startling conclusion that for light itself, u=0, so that light is stationary -- the only thing that doesn't "travel at the speed of light" is light!
Secondly, the fact that u^2 = c^2 alway for all massive objects is "merely" a statement that dynamics occurs in SR rather than Newton's theory. Marginally more important is the direction in which the four-velocity is pointing -- in other words, where something is going. Using u = 4-velocity, v = "normal velocity" and y as the lorentz factor (related to transformations,and depending on v), we have:
u^2 = y^2*(c^2 - v^2)
and to me the v carries more useful information about the motion of the particle. In particular it's the "v-velocity", rather than the u, that joins up best with Newton's theory of motion. And ultimately the point of SR is that it extends, rather than replaces, Newton's theories.
I don't know. It's all down to interpretation I suppose. The 4-velocity is important because you need to know what is invariant. The 3-velocity is important because you need to know where something is actually going.
And before people jump on me along the lines of "but surely the point is that all motion is relative!" -- yes, but not everything is stationary "at once", so that while no object can be said to be moving absolutely, all objects are moving with respect to something. And what that something is determines v. Since, usually, that something is us, we care about what v is rather more than what u is, since u is always the same anyway.