You can put them in parallel but they may not even be necessary. Have you measured the voltage of the 12V output and tried to turn on all of the fans at once and see what it drops to?
If the 12V PSU is adequately rated, I'm thinking it won't be much of an issue.
If capacitors were needed, I would put them on the output of the 12V supply, prior to the thermostat, to avoid switching into the capacitor which will cause a large amount of current to flow for a short time.