Because your question about the speed is unspecific but generally targeted at humanoid robots, so I think that the most direct solution is to count or measure the specific task performed by the robot and to record the time taken by the robot to complete the given task.
Having that, you should be able to determine the rate of the robot's performance, whether walking a distance, climbing stairs, picking & delivering objects, or “speaking” a number of words. If the robot's tasks are unmeasurable, then you have to look into the robot control system and determine its Observability rank. An observer may be designed to estimate the rate of the robot's performance.
You can probably get an inexpensive gadget like Fitbit and strap it to the biped robot. Recently, MIT has developed a wireless walking speed measurement system called WiGait, which is way more accurate than a Fitbit (within 95% and 99% accuracy).
Technically, you should use a Direct Drive Motor equipped with a pulse encoder to measure the walking distance and a tachometer to measure the speed. Alternatively, you can probably use the Freelap Timing System for accuracy (see Figure).
Generally the velocity of the robot trank is not constant during the walking motion. The velocity changes depending on the Trank position with respect to the position of the standing foot.
You can determine the average velocity simply by measuring the step length and divide it by the time needed to take the step.