I looked at the site, and any MOSFET on the page with "Power MOSFET TO-220 package" seems to fit (sufficient voltage and amperage) for this circuit (powering a fan). Of course I have NOT looked at every datasheet, or even a single one, so I assume the Vgs for full on (the rated A) is 10V - it usually is - and that the power/wattage is so small that the Rds (effective resistance equivalence) does not matter (no significant heating of the MOSFET). So look at those values (low Rds, Vgs~10V), otherwise choose the cheapest.
Secondly the site has a page with "Logic Level Power MOSFET TO-220". These are the greatest thing since sliced bread, as they will interafce directly to the Arduino the point being they have a Vgs lower than 5V. The circuit simply reduces to the Arduino pin goes to the Gate, leave 12V and fan and 0V as before. All the other resistors, capacitors and transistors are ommited. It is prudent to put a 10K resistor between gate and 0V so the MOSFET is fully turned OFF when the Arduino pin is in INPUT mode (as it is during power up until your program starts)
Some computer fans specifically warn against using PWM on them without any smoothing, I've only seen the warning in fairly high end server fans, but it might be worth trying to find a datasheet for your fan(s) if they're expensive.
While this circuit inputs PWM the fan is not driven by a PWM signal. There is a filter first then a FET running in the linear region. This circuit was designed for a high end fan so as not to apply PWM directly to the fan.
Well, that is interesting. I assumed the transistor was to boost the 5V to 12V for the gate. I didnt think about the resistor values which (with that infamous clear hindsight) do not support that. Well, that expains the capacitors, too. I just thought the circuit had gone overboard with decoupling
You don't decouple signal lines, only power lines.
You don't need a heatsink for a 120mA fan which is what it was designed for.
The filter is first so you can use a high value of R and so only need a smaller value of C and have a high output impedance. The transistor then converts that impedance as well as boosting the signal for the FET.