Here is a good article, though written for Basic Stamp, about using PID. Believe me, this part of your project will be the most interesting.
http://learn.parallax.com/tutorials/language/pbasic/pid-control/proportional-integral-and-derivative
I have built many devices that ride around in all sorts of vehicles. You will not have a problem there.
You need a speed pickup, which could be something like a Cherry KB15MKW01 Gear Sensor. It can sense a piece of metal flying by and generates a nice open collector signal. Just attach it to your Arduino and use a pull up resistor. It is a hall effect device and any sort of rotating shaft with a bolt in it (or similar) will give you a nice speed reference.
I would buffer your Analog throttle output with another OpAmp. Always nice to have a couple of pots on there to adjust the range without having to get out your computer. And use use a simple double throw relay to switch out your gas pedal and in your Cruse Control. That way, your emergency / kill system could easily just revert to your gas pedal when you take away power from the relay.
An Opto Isolated pick up off your brake light will give you a signal to release the Cruise Control when you touch the brake.
Then a couple of buttons to turn things on and off. You might also like to use a pot to set your speed in your first model, instead of trying to capture your current speed with a button press. Do both, simple logic.
I have done all this but my programming ability is limited and the PID work I have done needs some help.
Forget the accelerometer and stuff like that. Your software should just keep track of how fast your system responds to corrections. Its a classic servo loop you have to close and all well written about on the internet.
Its a great project.
Greg