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.