Doesn't that mean that it froze quickly, centuries ago, and stayed frozen until now?
Not necessarily. In places where permafrost exists, the thickness of the 'active layer' (the layer above permafrost that thaws seasonally) is relatively stable. This means that if you add material and raise the ground surface by burying organic material and soil, the top of permafrost will raise. So you can accumulate organic material in permafrost in a stable climate!
Also, consider that the process of organic material decaying once buried can take quite a lot of time, meaning that burial rates don't have to be as rapid as you might think. Modern-day sphagnum peat bogs accumulate a lot of organic material in them even in temperate climates.
What process caused such a sudden, centuries-long freeze? Don't we need to know this before we understand why it's reversing now? Presumably we humans had nothing to do with the freeze!
As stated above, the drop in temperatures doesn't have to be rapid because organic material can accumulate in permafrost even in a stable climate.