That is listed as 12V DC solenoid so you definitely don't want to try plugging into AC mains directly as fire and/or death may follow. Unfortunately it doesn't seem to mention the coil current, if you have a multimeter you could set it to the 10A range and connect it to a car battery with the meter in series to measure.

But otherwise I have a solenoid of fairly similar size (although a gas one) and I just measured it as around 1.5A. I'd hazard a guess those would be under 2.5A so I think a 12V DC power supply with a current rating of 5A would be sufficient for the pair of them.

As you've already sorted out controlling a 5V relay using the Arduino it sounds like a power supply is all you need. They are available from most electronics stores, e-bay etc in many styles but here's an [example on Amazon][1].


  [1]: http://www.amazon.com/Amico-Power-Supply-Adapter-Strip/dp/B00D8322VG/ref=sr_1_12?s=hi&ie=UTF8&qid=1384929892&sr=1-12&keywords=12v%205a%20power%20supply