Update with a more clear answer:
Here's a plot of all the velocities involved with shock propagation through a sationary medium:
The x axis is the mach number of the shock wave and represents the strength of the shock wave, it could have been velocity or pressure ratio or any other quantity that is monotonic with shock strength.
The y-axis is velocity relative to the still air.
* In solid red we have the velocity of the air entering the shock wave which in this reference frame is still, and thus 0.
* In solid blue we have the velocity of the shock wave.
* In solid green we have the velocity of the air after exiting the shock wave.
In dashed lines I've added to the graph the maximum and minimum velocities that a sound wave could travel (moving with the shock and opposite the shock respectively), but the velocity of a sound wave is relative to the average velocity of the medium it is traveling through, so I've added these line colored according to the medium they are traveling through.
As noted by the OP and the quotation above the velocity of the shock (in blue) is always higher than the velocity of sound in the entering air. However, it's always less than the forward velocity of sound in the exiting medium.
Thus a pressure wave generated by a plane increasing in velocity can propagate to catch up to the shock wave and push it to go even faster. Similarly, if the plane slows down the lower pressure wave can also catch up to the shock wave and slow it down. This is the same propagation mechanism as in longitudinal sound waves.
The fact that the shock wave is traveling faster than sound in the sill medium isn't a problem because the shock wave is being generated and pushed forward by the exiting medium, and relative to the exiting medium the shock wave is traveling at less than the speed of sound.
Change in speed of sound
The fact that the speed of sound changes across the shock wave is irrelevant to this analysis. It was accounted for in the creation of the graph as can be seen by the green dashed lines diverging. However, even if they had not diverged at all the shock wave would still be within the speed of sound in the exiting medium. Similarly, if the speed of sound of the exiting medium was applied to the entering medium, the shock will still fall outside that speed of sound. (Doing this doesn't make physical sense, but is just to demonstrate that the change of speed of sound is irrelevant to answering the question.)
Sudo speeds of sound are dotted (sound velocities traveling in the opposite direction as the shock have been removed for clarity):
Old Answer
Sound waves travel at the speed of sound relative to the the average velocity of the medium. 441
In the case of a shock wave, the time average velocity of the medium is different on the two sides of the shock wave.
Shock Wave's Perspective
In the frame of reference where the shock wave is stationary, entering medium travels towards the shock wave at super sonic speeds, and exiting medium travels away from the shock wave at sub sonic speeds. This is the usual frame of reference used to analyze shock waves and is used in shock tables
Exiting Medium's Perspective
In the frame of reference of the exiting medium the shock wave travels outward at sub sonic speeds and the entering medium travels inward at super sonic speeds. Entering Medium's Perspective - Finally, in the frame of reference of the entering medium, the shock wave travels inward at super sonic speed, and the exiting medium exits at a lesser super sonic speed. This is the frame of reference used in the article as the entering fluid is the atmosphere that the plane is flying through and is thus the assumed rest frame.
Conclusion
The shock wave travels at the speed of sound relative to a weighted average of medium velocity, and is thus not an exception to the rule that wave travel at the speed of sound relative to the average velocity of the medium.
Note that the speed of sound does depend on temperature, and that the temperature changes across a shock wave $a=\sqrt{\gamma\,R\,T}$. However, this effect is not as large as the velocity differences due to the change in reference frame. The figures provided above are to scale using Mach numbers for an entering speed of mach 5. Thus those arrow ignore the change in speed of sound. However, if the changes in speed of sound were accounted for my conclusion would still holds. 562