If you plan to use mechanical relays, such as those linked to above, the Arduino will not be capable of driving the relay coils directly. An Arduino I/O pin can only sink or source about 20mA. Most mechanical relays will require much more current than that to energize their coil. For instance, the relays in the link given above require anywhere from 40mA to 178mA to turn them on. Therefore, you will need an intermediate component to take the low current signal from the Arduino and provide the necessary current for the relays.
Here are a few parts capable of taking an Arduino output and converting those into something capable of driving relay coils:
The other thing I would suggest is to make sure you use a relay that is rated somewhat above your assumed load rating. Your solenoid is spec’d for about 6A at 12Vdc. I would make sure the relay you pick is rated for 10A or more for INDUCTIVE loads. This spec is often buried in the datasheet. For instance, the G2R-1A-T DC5 can handle a 10A inductive load as long as the DC voltage does not exceed 20V. So in your case this would be a reasonable choice. However, had it been a 30V solenoid, this relay could only handle a 5A load.