Your first step should be to put a multimeter across the terminals on a fan. If there's power present, you'll know that it's a fault with the fan. If not, you'll know it's a fault with the circuitry supplying power to the fan.
Assuming the latter, you should then look for a physical problem, such as a loose connection somewhere. Beyond that, things can get a bit tricky, as you'll need to consider what's inside your computer that can affect the relevant circuit. It could be a problem with a component or it might be related to the BIOS. (Examine the BIOS to see if there are any temperature settings that might be relevant).