Hi,
What you want to do is very much doable with pretty much any PIC, a 16F877 will be plenty. Make sure you read thru the complete PID filter thread (if you haven't already) as it covers several things - and provides an updated version of the PID filter in post #57.

The easiest way is to use a solid state relay as it isolates the load from the PIC and is easy to drive (it's basically just a LED). But to give a more detailed answer we'd need to know if the heater is AC and you by PWM really mean phase angle control. Or if it's DC and you intend to use the CCP-module in the PIC to produce a PWM signal - or (if it's either AC or DC) you intend to create a slow speed PWM with a period of several seconds or longer (I beleive this is what Malcolm did) where the fact that a triac or solid state relay for AC doesn't switch off until next zero crossing doesn't matter.

/Henrik.