When you turn on your ignition you are really just supplying ~12vdc to different areas of the car.
You have 4 states:
Off: everything is off
Acc: accessory relay has power, supplying your cigarette lighter port, stereo, etc.
Run: this triggers relays for all of your engine's necessary electrical components. In this state Acc is also active.
Start: this triggers your starter motor and allows your engine to turn over. In this state Run is active but Acc might be switched off as to not overdraw from your battery (depending on your car).
If I were to approach this problem I would break it down into 4 logical steps.
Supply power: I would hook it up to a voltage regulator with a few capacitors to the Run circuit to get a clean 5v line out of the 12v battery line. You could even wire this in to your ignition switch harness directly.
Input: If you pull down the voltage from the Start line and use that as input, if you program your arduino to "arm" when the Start circuit powers up, then trigger the audio when the Start circuit powers down, you can reasonably assume that it wont play the sound until the engine turns over. If your battery starts to die, you might hear the sound a good 20 times trying to get your car to start though.
Output audio: this part is up to you. You could rig up a little amp and a small speaker in the dash if you wanted simplicity, or you can try to hack your head unity. Lots of cars dont have their amps powered while the car is starting to make sure that the starter motor has enough amps. Keep that in mind and be creative.
Turn off: if you do use an amp and speaker in the dash, would make sense to power all that down while not in use.