PID tuning without plant model
PID implicitly expects to be controlling a linear system.  It seems that your system is not linear.  If you ignore that, you will end up tuning the system for sluggish operation over one part of the range to ensure some other part of the range remains stable.

The first thing to do then is to linearize your plant.  Measure a bunch of valve settings and resulting temperature, with whatever is producing the heat held constant.  Then invert that table and put it between the PID controller and the valve setting.  Now the PID controller thinks it is driving a linear system.

As for tuning the PID, there are whole books on that.  There are equations you can use to get the PID coefficients if you know some things about your system.  However, in practice that just gets you a starting point.  Real PID tuning always includes some experimentation.

Since your system might be rather slow, it would help to get a lot of the PID tuning done on a simulation.  If you can linearize your plant, then you can use the method I describe in How to use measured step response to tune control system.