I used a 2n3904 or a 2n2222a transistor with a 1k resistor from base to the output pin on the arduino. Emittor to Ground, + direct to the solenoid and collector to second wire from solenoid. These are NPN style.. You can also use a PNP style and just reverse ground and +12v on the ends.
This will supply up to 500ma with standard to-93 transistor.. There are other transistors to use if you need more current.. Or you could just 'double up' the transistors.