Watchtowers will help you spot the rebels and are a good idea in general, but in Medieval 2 rebels will spawn at random somewhere on your map. They are not hugely common, but they happen without any cause.