How to measure propagation velocity through a trace on a pcb?
To do this measurement, there are two well-established methods:

TDR

Apply a pulse input (either the rising or falling edge of a square wave), and measure the time for the edge to propagate to the far end of the trace. The delay measurement is done with an oscilloscope, and high-end oscilloscopes have TDR plug-in modules available to automate this measurement. 

Key requirements for your measurement equipment is that the pulse source should have a very fast rise time, and the cables connecting it to your system under test should not slow the edge down too much. The oscilloscope must have sufficient trigger accuracy and timebase resolution to measure the arrival time with the accuracy you want.

Group Delay

Use a vector network analyzer (VNA) to measure the phase response of your trace. The group delay (derivative of phase with respect to frequency) gives the propagation delay through the trace at each frequency. You'll be interested in all the frequencies contained in your signal under normal use, so for digital signals that would be from some low frequency determined by your coding scheme up to a high frequency determined by the rise and fall times of your edges.

In this case the quality of the stimulus is less critical than in the TDR case, but you do need to carefully calibrate the VNA and interconnecting cables on a daily or half-daily basis, using a quality calibration kit, to be sure of getting a meaningful measurement.

More difficulties

If your traces are layed out as tightly-coupled differential lines, you would want to do these measurements using differential stimulus and measurement. Unfortunately, appropriate gear to do the measurements differentially is not widely available. If your traces are single-ended, or differential but layed out as uncoupled lines, then a single-ended measurement is appropriate.

Also, as Mazurnification points out in his answer, how you connect your test gear to the traces is critical. If you can arrange to test between two connectorized ends of the trace, that's the best. If you are trying to test traces between chips on a populated board, that's almost impossible. If you have an un-stuffed board, you may be able to connect to it with some kind of probes. But more likely you will just build some test coupons onto the panel with your boards that let you connectorize traces of the same geometry as the ones you are worried about.