I've got a similar project in the works, only I need to send commands to a radio via RS232.
You want to power the arduino with a voltage regulator, but there's one built in to the arduino NG so you can hook up your car's 12V system to the coax power jack (or the "9V" input header). Make sure you move the power select jumper so that you're getting Vcc from the regulator instead of the USB connector. You may also need to add a resistor (10k or so) between pin 0 and ground to keep the bootloader from hanging up the arduino.
For your power sense circuit, use a voltage divider as shown above to feed the analog input pin. Don't try to power the arduino with a voltage divider especially in a car, as there are wide voltage swings (from 10V to near 20V every time you start the engine) that would cause problems.
In addition to switching the load with a relay you can find solid state switches, some of which are designed to take TTL levels directly and switch large loads up to 40A or more. Some example part numbers are
IPS5451L
VN820
These are 5 lead devices and will need a heatsink to switch maximum loads.
I've got one of these APO2: Automatic Power Off Device - APRS World, LLC which performs load switching based on vehicle system voltage. That has since been replaced by a relay-based model APO3: Automatic Power Off 3 - APRS World, LLC This might be a useful project to get ideas for the load switching part of your circuit.
You can also switch the load with a small transistor turning on a bigger transistor, and the big transistor would switch the load to your power supply. The power switch ICs just mentioned are basically this arrangement in a single package.
-j