Using the same power source for microcontroller (arduino) and rest of the circuit?
You may be able to run the microcontroller (μC), motor, solenoid from a single power source1.  That's probably the first approach that you should try.  Make sure to include back-EMF diodes for motor and solenoid.

1 Of course, you need to generate the appropriate supply voltages from that power source.  I assume that you understand this.

Solenoids and motors can in fact generate voltage spikes, which may cause problems for the μC.  For example, spikes can cause a brownout.  (Such spikes are a type of conducted interference.  The term "noise" is often used for such nuisances.  More rigorous definition of noise here.)   Whether you will encounter these problems or not depends on the size of the coils and the capacitance between the supply rail and ground in your circuit.

Here's a related thread, where someone ran into problems with spikes generated by a solenoid valve.

edit:
Here's a detailed answer in another related thread.
Here's a page on EMI suppression for motors.