How do we know that the rate at which a body loses heat is proportional to the difference between its temperature and that of its environment? Did someone do an experiment, or was that fact derived from other ideas we had about how the world works? 
 A: 
How do we know that the rate at which a body loses heat is proportional to the difference between its temperature and that of its environment?

In classical physics this is a law.

"Fourier's law
  The law of heat conduction, also known as Fourier's law, states that the time rate of heat transfer through a material is proportional to the negative gradient in the temperature and to the area, at right angles to that gradient, through which the heat flows. We can state this law in two equivalent forms: the integral form, in which we look at the amount of energy flowing into or out of a body as a whole, and the differential form, in which we look at the flow rates or fluxes of energy locally."$^1$


$^1$Source
A: Ultimately, Newton's law of cooling is a simplification that can be obtained from the full heat equation, i.e. $$\rho c\frac{\partial T}{\partial t} = - \kappa \nabla \cdot T.$$ 
The heat equation itself can be derived from first principles, assuming Fourier's law for heat flow, namely that it is proportional microscopically to the difference in temperature between two arbitrary regions. Fourier's law itself can be derived from modern statistical mechanics, although it's a little bit involved to do so: have a look at this.
Historically, Fourier's law was "just" an experimentally derived truth. 
A: It appears Newton himself did some experimentation, but failed to divulge exactly what he did - though he said "he used a linseed oil thermometer" and the resulting data.
Source: History of Newton's Law of Cooling
