Gul Madred more or less stated that the Military came to power during his lifetime. Assuming he was the same age as his actor, David Warner, who was about 50 at the time, this would suggest that it happened about 40 years in the past.
According to Memory Alpha, the Occupation of Bajor by Cardassia ran from 2319 to 2369. That is 50 years. Cardassia maintained a military presence 10 years prior to this. Cardassia was militaristic and hostile, annexing star systems by force years before establishing a military presence on Bajor.