Electric Fans always on because of Fan Controller?

IMO the easiest place to start is, with engine cold, disconnect the wire going to the sensor. If the fan stops, the sensor is bad.
Assuming it keeps running, verify that the power goes into the common terminal of the relay and the fan is wired to the normally open terminal of the relay.
If the wiring is correct, then at this point, I would try another relay.