Any idea what type / number transistor I should use?
Well I think CR was telling you that......
Yes, you can PWM the transistors.
How'd relays come into this?
Use the example on pin D12. Emitter connects to Arduino Gnd and to power supply Gnd.LED strip+ goes to 12V, LED strip- goes to the collector.