I would use 6-7(depending on how many gears the car have) hall sensors, mounted around the gear lever(under the gaitor).
And if the car has DBW(Drive by wire) the gas pedal potentiometer would most likely be 5 volt, so its sends a voltage to the ECU, thats from 5v to about 1v, acording to how much the throttle is engaged.
If you connect it over the DBW system, then you can make it find the "right" rpm, both on up and down shifting.
There are 2 ways, of finding out what rpm the engine needs to rev to, either by knowing the ratio on the gears, or by having a "map" hardcoded in to the arduino(This can actually be recorded by the arduino if you lets say is in 4 gear 2000 rpm push a button on the arduino, changes to 3, and keep the speed in 3 gear, push the button again, to let the arduino know when to "record" the data.)
By having these numbers, you can calculate the ratio.
If your car have cruise control, then it will allready have a clutch sensor, and also most likely DBW.
If the car dont have cruise control, then you can easily add it, because you allready have all the sensors.
Hmm, that was a lot of info, well just ask if you need some more info, i work as a auto mechanics.