Effects of Fortifications
Fortresses have a variety of effects, mostly related to siege warfare and supply.
Fortresses are primarily useful defensively. An unfortified city will be captured immediately when any unopposed enemy force enters the province. (Of course, it's also easy to recapture.)
Fortifications prevent enemies from capturing the city unless they stop and siege or assault. Assaults are risky, and rarely succeed without a substantial advantage in leadership, tech or numbers. To siege even the most minimal fort requires many months. Higher level fortresses increase the initial defense rating of a city during sieges, thus a siege will take even longer.
Higher level forts also require the enemy to bring increasing numbers of artillery if he wishes to get the artillery bonus to siege. In assaults, the fortress level is subtracted from attacker rolls as a negative DRM unless there is a breach. Thus, assaulting a high-level fort without a breach is more or less suicide.
Higher level forts also require more troops to cover (1 army unit*[fort level]) or siege (5 army units*[fort level]). Forts also deny the enemy the ability to move around small armies; armies too small to cover a province are not allowed to move into it unless there are friendly or enemy armies already in it. If the combined size of all friendly armies in a province is reduced below its cover level, all of the armies will be forced to retreat.
Effects on Friendly Forces
Offensively, the amount of friendly troops a province can supply is increased with increasing fortress level, making it easier to assemble large armies. The increased supply created by fortresses does not apply to enemies (unless they have military access), and (strangely) this holds true even if they capture the city.
Any large difference in supply in a province makes attritional warfare possible, where you enter a province but then retreat from battle, using your armies' presence to "eat up" all the supply for that month, and inflict high attrition on an enemy. See the article on How to do Attritional Warfare. In particular attrition is very helpful in dealing with rebels, because losing battles against them is free, but they fight at parity with the player. See the article on How to Handle Rebels.
Outside of sieges and supply, fortresses have little effect. However, the fortress level of a city does increase its owner's chance of a successful religious conversion, by 2% per level. Also, the size of the fort determines the quantity of rebels generated in a province by a rebellion which does not immediately capture the fort (which is rare). When this happens, there will always be enough rebels to siege whatever fortress is there. Thus, a level 6 fortress will always get 30000+ rebels per rebellion (ouch!).
Changing Fortification Levels
Most cities have level 1 fortresses in the 1419 scenario, although there are several areas of the world (China, Persia, and South America) that start largely unfortified. Fortification levels are much higher in many of the other scenarios. All new colonies, and thus all new cities, are unfortified.
The fortification level in a province can changed in several ways.
There are two ways in which fortresses can be improved. One is via events. Some countries get scripted events which increase their forts. All countries get random events, and if a country has a defensive domestic policy, it has a chance to get free fortress upgrades.
The typical way in which fortresses are upgraded is via the owner paying to do so as a city upgrade project. Forts up to level 5 may be upgraded (level 6 is the maximum), so long as the size of the existing fort is lower than the base tax value of its city. The monetary cost of a fortress improvement increases with the fortress level (see the table) and is modified by inflation and the position of the Defensive/Offensive doctrine domestic policy slider. Improving a fortress to the next level takes 12 months.
There are no events which degrade fortifications, and it is not possible to intentionally reduce a city's fortification level. However, whenever a city is captured, there is a small chance that the fortress will be knocked down one level of size, but only if it is at least level 2.