Connect 5V DC Fan to Ardumoto
If you look at the schematic on the product page it shows that the Vin from the arduino is connected to the same Vin on the shield and the Vin to the motor driver. So it is either or where you want to connect power.

With regards to controlling the fan, brushless fans are polarized because of the internal control circuitry, this means that it cannot be made to reverse, therefore you should always give the direction pin a high signal. The Sparkfun hookup guide has a example code which shows how to control the motor shield, and some explination.