You are discussing things that are very close to a classical controller. But lets start from basics.
You need to control temperature to agree with a target setpoint. For this you need a controller. The basic thing to keep in mind is that a controller applies a defined control law on the difference between setpoint and actual value, and produces the plant command variable as the result. The command variable in this case is the duty cycle of the pwm signal controlling the fan speed, from 0 to 100%.
We will get to elaborations but that is all the actual controller does. I am sure you don't want to involve matrix calculations so lets keep it simple and use well defined and understood control laws only. That would then be the proportional-integral or PI. There are 2 easily understood terms here.
Proportional control or P-term is just a defined ratio between error signal and control signal, i.e.
C = Kpe, where
e is the error signal (Setpoint - Actual),
KP is the multiplier or constant of proportionality.
Proportional control has a shortcoming in that in order to produce a command signal there must exist an error signal. This is easy to see from the equation, since if e = 0, so does the command signal. You can make the necessary e smaller by increasing the gain, i.e. the P value but as that increases the gain of the feedback loop, there will be a limit after which the system is no longer stable.
Enter the integrative or I-term. This is the time integral of the error signal multiplied by a gain, i.e.
C = Ki/Ti * integral( e) dt, where
Ki is the integration gain,
Ti is the integrator time constant
The integral action will reset to zero the steady state error left by the P term. A PI controller is just the sum of the P and I-terms.
It is a known fact that tuning a PI(D) controller can be somewhat challenging as setting the gains too high is a quick route to oscillations or command runaway. This risk is significantly increased in the presence of time lags in the process, and this seems to be the case with your application. So too much should not be expected from the control dynamics but this scheme will work.
Now, there were some process disturbances. All of these will be handled by the PI controller but if you need better dynamics than what you can get by tuning the PI, there are 2 more things you can do: introduce the D term and/or use feedforward control.
The derivative or D-term is the time derivative of the error signal i.e. it reacts to the slope of e, or in other words changes. The equation is
C = Kd * de/dt, where
Kdis the derivation gain,
de/dt is the first derivative of the error signal.
This term will make the controller more responsive to changes in setpoint or actual value, increasing the control dynamics. Same cautions regarding stability as above.
The final trick is to use feedforward control. This method has saved the bacon several times for me in situations where classical PID dynamics just cannot cope. Using this method you bypass the contol loop and apply a direct command signal based on either the setpoint or the actual value. Say you know that if the coolant temp is X degrees, the fan must run at Y% of full speed to cope. So why not feed the actual temp value back to the command signal with suitable gain to make it so.
So the feedforward correction signal would become
C = Y%/Xdeg (provided the speed is directly proportional to the temperature).
Any errors this calculation makes will be easily corrected by the controller - actually far easier than the case where you feed no signal, because then the controller must remove all error instead just the residual one.
An analog PID controller is easily constructed out of an op amp, 2 caps and 2 resistors and some auxiliary stuff. For a software controller it is a bit more complex as you will be going discrete time, but the wonderland of Inet is full of implementation examples, some of which actually work. I seem to recall that even the Arduino provides a PID controller, so that might be worth lookin into. as the source code is freely available.