Devastation is the blackened area that shows up on the campaign map when an enemy army sits in the territory too long. Your own troops seiging a city create devastation.

Rebel armies *anywhere* in the province can create devastated patches - so if the province is a big one, make sure you can see all of it lest a rebel army juts hang out generating devastation. (I had one do that to me once - I had all the roads covered, but he was off on a hill devastatin' away)

I think once the offending army is removed, the devastated area clears up with time.