Velocity does indeed have to be measured relative to something. We can measure our radial velocity relative to any other astronomical object we care to, by measuring Doppler shifts. But if you want to know our velocity "relative to the Universe as a whole" rather than relative to any one object, we have to be a bit careful to define our terms.
Because the Universe appears to be approximately homogeneous and isotropic, it makes sense to define a "rest frame" at any given point. (The rest frames at different points are moving with respect to each other -- that's what it means to say that the Universe is expanding.) This "rest frame" is essentially the frame in which the stuff surrounding that point appears to be moving isotropically (the same in all directions). In practice, the best way to define that rest frame is to find the frame in which the cosmic microwave background appears the same in all directions (has no dipole moment, to be precise). Relative to this frame, the local group of galaxies is moving at about 600 km/s (Wikipedia gives precise numbers and probably citations that I'm too lazy to look up).
People sometimes worry about whether the existence of a preferred "rest frame" of this sort is in conflict with the principle of relativity. The answer is that it isn't. There are a couple of ways to see why. One is to note that the principle of relativity says that the laws of physics have no preferred frames, but particular solutions to the laws can have preferred frames. Another way of putting it, which I prefer, is that the "rest frame" we use in cosmology is simply the center-of-momentum frame of a bunch of particles (namely the CMB photons in our neighborhood). In other contexts, we're not surprised or worried by the fact that a bunch of particles have a rest frame, so why should we worry about it here?