Your sensation of heat is dependent on the change in temperature of your skin, which is roughly proportional to the difference in temperature between skin and material.
However, temperature difference is much less important than the transfer of heat between your skin and an object, which is heavily dependent on the type of material you are touching.
Why does a cold piece of steel feel so much colder than the surrounding air, despite them being in thermal equilibrium? The answer is that steel is a much better conductor of heat, and can therefore draw heat from your hand at a much faster rate than air, which is a poor conductor of heat.
A very interesting study by Lele, Weddell and Williams (1954)  demonstrates that the rise in skin temperature is proportional to the rate of heat transfer. The same paper suggests that the sensation of heat is roughly proportional to the rate of heat transfer.
Now for some physics.
Heat transfer along an object of length L and cross-sectional area A is given by:
Q = kAt$\Delta$T / L
where Q is the heat content, t is time, and k is the thermal conductivity.
As you can see, the transfer of heat is proportional to the difference in temperature between the two ends of the object. So a simple interpretation would suggest that your body senses the rate of heat transfer, which is directly proportional to the difference in temperature between your skin and the object you are touching.
However, this neglects the ability of your body to draw heat away from an area (via blood circulation, passive heat conduction etc). Given that your body maintains a core temperature of around 37 degrees Celsius, this complicates matters somewhat, and probably comes into play when you touch a hot/cold object for an extended period of time (e.g. your example of washing your hands to warm up).
So in summary, you are essentially correct, in that your body feels the difference in temperature between your skin and the surroundings, taking into account the thermal conductivity of the surroundings.
 Lele PP, Weddell G, Williams CM. The relationship between heat transfer, skin temperature and cutaneous sensibility. J Physiol. 1954;126: 206–234.