One obvious thing you'll also need is a method to override it for a short period of time. Without this you can't turn the PC on.
It could be as tricky as having the microcontroller turn power on, control the power on signal from the power supply, and wait some time for the fans to come up to speed.
Or it could be as simple as a momentary contact switch across the relay contacts.