I've seen it done with the relay just being added to the "high" setting. The idea was to get the motor running a little faster with out the drop through the switch.
If you wanted to use the relay for all the speeds, you would have to add a relay for each speed. A three speed switch would have three relays and the relays would have to be before the speed resistor. There's other ways of doing it, but that's the easiest way that uses the existing wiring and switch.
Honestly, if you've replaced the bad parts and checked the wiring, you're set. If you wanted to add one relay for the high speed, that might make some sense, but I can't see any reason to.
