How are subsurface wave speeds determined without subsurface sensors?
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.