I assume from your question you want the essential parts of an Arduino along with your circuit in a permanent form.

Here are my steps:

1. Build the entire circuit on a breadboard or two. Then you know it all works.
2. Transfer it to a permanent form of circuit, testing as you go.

Take it a step at a time, and it'll work out nicely.

1. Build the entire circuit on a breadboard or two.

Then you know it all works, and that you have all of the components ready to make your permanent circuit

This will involve making and programming part of your Arduino on the breadboard. I don't think you'll need the USB part, so it can be through-hole components which are relatively straightforward to begin with.

Here is a link to instructions which show how to make an Arduino without USB.

It can be programmed using your existing Arduino, you don't need a programmer. For example: http://arduino.cc/en/Tutorial/ArduinoToBreadboard

I'd make a sketch of the circuit schematic to ensure I understood what I had on the breadboard, and to guide the next step.

2. I'd recommend you transfer the whole thing to 'veroboard' (stripboard) rather than make a PCB.

Veroboard/stripboard will be much quicker and cheaper. You could easily spend 10x longer learning to use Eagle well enough to get a PCB made, than it would take to design and make the entire circuit on veroboard/stripboard.

You can do a design on squared paper, but there are some CAD programs to help if you google for veroboard CAD. I have never used them, I use paper and a soft pencil or a vector drawing package. A friend used PowerPoint because that's what he had to hand.

Here is an example of someone who has built an Arduino on veroboard/stripboard.

It shows the design he produced for veroboard/stripboard. Try to get a reasonable layout for your design before making it. This is where the soft pencil and eraser come in :-) Typically the first couple of attempts are too big or too small. Make it easy for yourself and get plenty of squared of graph paper :-)

This link shows what the process will look like.

You can follow veroboard/stripboard arduino design, and test that it works. Then focus on your extra circuit.

Use a socket for the microcontroller, and so don't solder it in directly. Most of the other parts are a few $'s total, so I'd get a few of each part for spares and practice (To put it in context, some electronics companies charge more for delivery than those parts will cost, so getting several sets of parts makes sense, especially if you intend to make some more things).

Total cost for the Arduino part should be under $10.

Good luck, and I hope you enjoy it.

Don't use the 12V\$\rightarrow\$5V regulator, the Arduino needs at least 7V in. Use the battery's 12V directly instead.

The capacitor's value will depend on the Arduino's power consumption. The Arduino webpage doesn't say what the Uno consumes, so you can't say right away what capacitor value it needs. In any case it's not designed for low power. I checked the datasheet for the voltage regulator, and that alone already uses 6mA. On the schematic I can see two microntrollers: an ATMega16U2 running at 16MHz, and an AtMega328P, also at 16MHz. The former may consume up to 21mA, the latter says 9mA at 8MHz, so it's safe to say 18mA at 16MHz. We already have 45mA, let's round it to 50mA for the other components.

If a capacitor is discharged at a constant current, then

\$ \Delta V = \dfrac{I \cdot t}{C} \$

You start at 12V, and the Arduino needs a minimum of 7V, so \$\Delta V\$ = 5V, I was 50mA and t = 3s. Then

\$ C = \dfrac{I \cdot t}{\Delta V} = \dfrac{50mA \cdot 3s}{5V} = 30 000\mu F \$

That's the minimum, I would pick a 47 000\$\mu\$F/25V capacitor. Add detection for power off, so that you can switch off all unnecessary outputs which also may consume current, a relay for instance.

If you want to know exact what the power consumption is, add a 1\$\Omega\$ resistor in series with the power supply and measure the voltage drop. A 50mV drop means 50mA consumption.

Also add a TVS (Transient Voltage Suppressor) at the Arduino's power input; a car's 12V is extremely dirty.

Add the diode clabacchio mentions. A series resistor of 10\$\Omega\$/5W will charge the capacitor in 1.5s when applying power.