I connected HVG of the breakout board with the ground of the fans and my power supply. HV to the 12V+ of the power supply and the outputs to the VCC inputs of the fans.
On the input side I connected ground to the Arduino Ground and the Inputs to two seperate digital Pins
Please show us a schematic. I' not going to try and draw one or visualize the circuit from your description. 
I'd be surprised if that thing can power a fan. I looked at the SparkFun website and I didn't see a current spec and I didn't see what transistors they are using.
...At this point the transistors (and maybe the opto-isolators) may be fried from excess current or from the back-EMF from the fan motor (since you didn't add a flyback-diode and there isn't one on the board).
Try replacing the motor with an LED (with the usual current-limiting resistor). i.e. Try the Blink Example modified for whatever I/O pin you're using. If the LED isn't switching on & off, stick the LED (with resistor) on the input-side of the opto-isolator to make sure it's getting a pulse. If the LED does work, leave the LED attached and connect the motor.
(My guess is thats because of the voltage difference between 5v PWM signal and the 12v Power Supply.)
5V is enough to turn-on the LED inside the opto-isolator. The 12V on the output-side is separate (and possibly isolated depending how it's wired-up).