Powering a standard Arduino from a car battery (e.g. 12 volts) ? If so you can just connect it directly; the regulator can handle 12v easily.
Connecting relays is pretty easy, you just connect a pin from the Arduino to a resistor, then to a transistor, and connect the transistor to the relay. Here's the standard implemenation:http://arduino.cc/playground/uploads/Main/relays.pdf
As far as which board, if you go with the Arduino + Bluetooth from your link then you're set, but you'll need a separate circuit to convert 12v to 5v. Here's one idea:http://www.instructables.com/answers/How-can-I-convert-12v-down-to-5v/
I can't help you with the Bluetooth link between the phone and the board but there are other people who've done something similar; "arduino bluetooth android" turns up several interesting hits.