I believe it is 10 years. You may have loyalist rebel even if you have more than 100% loyalty. It depends on a bunch of factors, but I found I must put an occupation army for about 10 years to keep the province safe. On unimproved province (early in game), it takes 4 years to build a fort (which help reduce rebellion), another 2 to build town guards, perhaps 4 years for a church or building the economy. I would appoint a loyal governor, make sure there is no 2-loyalty units in the area, and make my King pay a visit (as soon as a port is constructed if it is on an island). I would have tax pardon during these years as well and send a general with high dread. A general that execute prisoners before.

These are the things I would do in the 10 years or so after I got a province.

Annie