Solenoid Getting Hot and Not Functioning Properly
The datasheet is under Documents Tab in your link near bottom of page.
https://www.sparkfun.com/products/100

You may choose either NC or NO using a SPDT RELAY.

The Valve is NC for water when the solenoid coil is OFF connected to NO (pin 3) with power off and Drain to THrow pin 2 and Source to GND and other end of Solenoid to Vcc.







simulate this circuit &ndash; Schematic created using CircuitLab



Schematics always show power-off condition so 2 to 4 = NC and 2 to 3 = NO
NC = normally Closed and NO = .... guess

with your schematic errors .. recheck but it won't work using 3 to 4

The relay is redundant as the MOSFET carefully chosen should be adequate to drive a solenoid, but using 12V open collector with pullup and careful power wiring direct from battery.

**Is 5V enough for Gate voltage? V GS = 5 V, I D =16 A  YES

typical ROOKIE errors.   no big deal...