Every single pentium 1 I have worked on, from 75MHz up to 200MHz, had a heatsink and a fan attached (or a peltier element). So lets assume they need at least a heatsink
Next: Whenever you use a heatsink you also use either:
- A thermal pad.
- A thin layer* of thermal paste.
The reason behind this is that a heatsink might look nice, flat and polished to the naked eye, but in practice the surfaces of the CPU and the heatsink are not a perfect match. There will be many small air pockets. These hinder the transfer of heat from the CPU to the heatsink. Thermal paste can be used to fill these holes. Therefor thermal paste is almost always used.
In cases where the heatsink itself is not enough and even a fan is added, you certainly want to use thermal paste.
So yes, do use thermal paste.
*: Thin because metal conducts heat better than the paste. So you want to use as little paste as possible, but enough to fill al the holes.