Your stability cost is calculated like this: Every province you own adds to the base stability cost. How much is only affected by what is the province religion compared to your state religion. Same religion gives low cost, different religion gives high cost. Your state religion then gives either a bonus or a malus to this base cost. Colonies and TPs also contribute to the stab cost, but at a lesser extent. You sum up all of your provinces base stab cost and it is modified by various factors. Inflation is one, also DP sliders (innovative, serfdom) play a role. If you have a lot of BB, then it will increase your stab cost. Having FAAs also modify the stab cost somewhat.
So gaining a province always boosts your stab cost and loosing a province lowers that.
For more details see the Economy FAQ.