Hmmm the grounds should be tied together.
If you really can't tie the grounds together why not drive the transistor that controls the fans through an opto isolator.
Connect the LED of the optoisolator to through a current limiting resistor to the Arduino output, and ground the LED on your Arduino's ground.
Then use the output of the optoisolator to drive the transistor and that can connect to the other ground for the 12V.
Check the web otherwise wikipedia has a nice intro
http://en.wikipedia.org/wiki/Opto-isolatorOtherwise even simpler would be to use a relay

Just remember one thing, maybe you know it already, when supplying the Arduino with 5V, the regulator on board has a drop out voltage, even though its low you will still need slightly over 5V of you are going to supply power into the regulator, otherwise supply the 5V directly to the 5V "bus" if you are going to use your adapter.