To start the car the ignition switch provides power to the starter solenoid. The starter solenoid acts as a very high current relay to provide power to the starter motor. By adding a small Arduino-controlled relay between the ignition switch and the starter solenoid you can prevent the starter motor from activating.
It might depend on the age and model of the car, but in my experience there is a relay that controls the starter solenoid (more properly called a starter contactor - I think this is a case of names being mixed up by mechanics not knowing wth they talk about, as the solenoid is on the starter motor to throw the pinion gear in mesh with the flywheel gear ring).
This relay is (in turn) controlled either directly by the ignition keyswitch, or more often today by some portion of the computer system in the vehicle (where the key switch just signals the computer to boot-up, self-check sensors, then it takes over the startup sequence).
I suppose that on the most recent cars, that intermediate relay has been superseded by a mosfet control or something; the only reason a relay was used originally was because the coil of the "starter solenoid" (starter contactor - it's basically a really large 100+ amp contact SPST relay) took a bit of current, that was easier to control with an intermediate relay than running the wiring back to the ignition keyswitch.
So - likely the best place to put the relay controlled by the Arduino - which should work for -any- vehicle manufactured in the last 50 years or more - would be in parallel with the ignition keyswitch contacts.