With anything mechanical like fans I would use a frequency that's not audible, either below 20Hz or above 20kHz. For resolution it would be easiest to do the full 100% range. Therefore, I'd choose something like 15Hz and 100 steps which gives an interrupt frequency of 1500 times per second. Assuming a 4MHz oscillator and a pic, you can use timer 2 with prescaler=4, PR2 = 166 and this will give you 1500 interrupt per second. In your interrupt have a counter that goes from 0 to 99 and when it wraps set all outputs that don't have PWM=0 high. Then each subsequent interrupt check all PWMs against the counter and set the ports of any that match low.
If you use a higher crystal frequency then prescaler=16 may help or use timer1 (16 bit) with the PWM special event trigger to generate the interrupt.
Have fun,
Mike.