Use a dedicated 12v power source (battery, wall wart, whatever) and connect it's GND to the Arduino's GND.
Alternatively, use one 12v wall wart to power the Arduino (via the DC jack) and use the "Vin" pin on the Arduino, which will then have 12v on it, to power your lights.