Considerations for powering solenoid and arduino from the same power supply
Presumably there is a regulator between the 12V supply and the arduino.  As long at the 12V supply remains high enough for the regulator to function, it will keep the voltage to the arduino constant.

However, regulators aren't perfect.  In particular, they can only compensate for input power variations up to some frequency.  Noise above that will be passed to the output.  If you think the input power might be noisy enough so that the regulator can't block it all, put a small filter on the input of the regulator.  Most regulators will work OK up to a few 10s of KHz.  You didn't say how much current the arduino draws, but you have plenty of voltage headroom.  A 10 Ohm resistor will only drop 1V at 100mA, which still leaves plenty for the regulator to work with.  That followed by a 10uF ceramic cap to ground right in front of the regulator will form a low pass filter with 1.6KHz rolloff.  That should be good enough to keep the input of the regulator down to frequencies it can deal with.

Of course the best way to handle noise is to not make it in the first place.  You absolutely need a diode or some kind of snubber to catch the inductive kickback when the solenoid is turned off.  The main reason is to keep from frying whatever is switching the solenoid, but a secondary effect will be to decrease overall noise.