You need to apply thermal paste to the outside of the cpu (between cooler and cpu, the thermal paste inside is only to spread heat from the die (CPU itself) to the IHS (integrated heat spreader: the metal square that is what the CPU looks like from the outside. Thermal paste usually only comes pre-applied to the bottom of the stock cooler that comes with the CPU, for an aftermarket one you usually apply it yourself.