MOSFET arduino RGB LED strip problem
The basic N MOS switch circuit is shown below. Please verify your connections.  



VDD in your case 12 V. Vin is the control signal from Arduino.

The schematics you are referring to is a P-MOSFET while, the datasheet you have shared (which you are using) is N-MOSFET.    

Below table indicates the gate voltage that is required to turn on the FET. Even for mere 1 mA the gate voltage may sometime needs to be 4 V (Arduino can provide a maximum of 5 V, some Arduinos,like Pro mini, Mega provide only 3.3 V). Since the LED strips datasheet is not available i am assuming at least it expects a few 100 mA for which chosen FET probably will fail to turn on. You have to choose another FET with lower VGS at required LED strip current. You cal also get away with gate drive circuitry to shoo the gate voltage from 5 V of Arduino to higher, but it will be not necessary, if you have access to other MOSFETs.




  For some reason the led strip turns on when I connect the power


Possibly due to wiring issue or the FET have already gone bad (failed and D and S pins are internally short). If the FET is still working for single LED then it is time to replace the FET with other FETs which have lower VGS requirement for significant currents that will match LED strip current you are using.
Below is one example of FET, which can be used instead (DMG3420U: datasheet): 

http://www.digikey.com/product-detail/en/diodes-incorporated/DMG3420U-7/DMG3420U-7DITR-ND/2279237