Yes, you can run both fans and the Arduino off one power supply. I would add some 1,000uF @25V capacitors across the fans just to kill some of the ripple the fans will produce. You can buy a 12V @2A switching power supply from Jameco or e-bay.
Are you simply wanting to turn the fans on and off or control speed? Controlling speed is more elegant and you can use the PWM capability of the Arduino to accomplish this. You might just use a transistor in "sink" mode instead of the MOS-FET especially if your Arduino is one of the 3.3V models. Finding a MOS-FET with a 2.5V Gate Threshold might be tough. A regular NPN transistor will saturate at >0.7V which makes it easier.