This is something I've never quite understood from a geology class I took years ago:
Consider the following picture (courtesy of wikipedia)
Obviously, we can't possibly have sensors deep in the mantle (or core). So, how exactly are these wave speeds determined?
This is a good question, and the basic answer is earthquake seismology. To answer this question, lets accept a fact: Waves propagate through the least time pathway, and not the least distance path. This property of physics is known as Fermat's principle.
When an Earthquake occurs, energy propagates similar to a ripple of water, and spreads. Each point on this ripple can be modeled as a ray, each following its least time path through the Earth. As these rays propagate, they reflect and refract off heterogeneities inside the earth. These reflections are important: we can detect these reflections using surface seismometers. Using multiple seismometers, and the location of the source (earthquake), we can calculate the "lag" between when the closest seismometer detects the earthquake and the others(further from the source). This lag time can be used as a proxy for the depth of the reflected wave's heterogeneity. Using how deep this reflection originates, we can then figure out the least time path of the wave in terms of actual distance. Velocity is just distance over time, even for seismic waves. So since we have the distance traveled by the wave, and the time the wave took to get to the receiver, we can complete the equation (distance/time).
In actual practice, this process is far more complex, as you have to look for many different waveforms: 
The picture above illustrates an earthquake sending waveforms through the earth. The SKS wave is a shear wave that refracts into the liquid outer core, turns into a compressional wave (since shear waves cannot propagate through liquid), and then is converted again to a shear wave as it enters the mantle and goes to the surface. A trained seismologist looks at the readings from seismometers to tease out specific waves, which we know the properties of, to determine properties of the planet's interior. The speeds of these waves are highly dependent on the assumed densities and other rock properties of the crust, mantle, and core.
Tomography! In essence, we guess some velocities, compute the arrival times our guess implies, compare them with actual arrival times, tweak our answer, and repeat. Seismic tomography is an ill-posed, ill-conditioned inverse problem, and one upshot of this is that the solutions are non-unique — there are infinitely many answers! We have to choose one (or, better, many), that are compatible with what we think we know about the earth. Compare this with a medical computed tomography (CT) scan, in which there are far fewer unknowns.
In the shallow subsurface, down to about 5–10 km in most basins, we have the added advantage of measured well logs, specifically sonic logs, which measure the slowness (1/velocity) of ultrasound. As in all inverse problems, extra information constrains the solution greatly.
