Many aftermarket heatsinks/fans DO include thermalpaste however, it is usually poor quality compared to buying thermalpaste separately. If you are ordering a new HSF, add a tube of thermalpaste (decent paste, arctic silver, antec) and you will be set for several applications. Often, if you are putting a HSF on for the first time, you will make a mistake and if you use the single use stuff that comes with the HSF (many come with a small packet opposed to a tube) you will be out of luck until new paste arrives. If you buy a small tube, you will be good for 4+ applications.
just my experience though.