Comparing that with http://en.wikipedia.org/wiki/Evolution_of_fungi "A rich diversity of fungi is known from the lower Devonian Rhynie chert", and lower Devonian = early Devonian, I very tentatively conclude fungi precluded trees. Given that, I (not hindered by much specific knowledge of the subject) expect that fungi breaking down cellulose co-evolved with trees.
Also, the key chemical wasn't cellulose, but rather lignin. Lignin is an astoundingly complex polymer* that plants use as "concrete" to create their woody cells. As far as I know, white rot fungi is the only group that can break it down.
*seriously, look at that thing: http://cse.ksu.edu/REU/S11/emd4y8/breakdown.html. That's a big goddamn molecule.
s/precluded/preceded/ (not to be confused with proceeded).
I speak as an expert. I spent one summer between grade school and high school cutting peat in a peat bog. It wasnt wet like the Everglades, but you could squeeze a handful of peat and see the water drip out.
The global debris layer created by the end-Cretaceous
impact at Chicxulub contained enough soot to indicate
that the entire terrestrial biosphere had burned.
Source:K-Pg extinction: Reevaluation of the heat-fire hypothesis; Robertson, Lewis, Sheehan & Toon, 2013; Journal of Geophysical Research: Biogeosciences
http://onlinelibrary.wiley.com/doi/10.1002/jgrg.20018/abstra...
Your typical coal bed is quite a bit thicker: http://en.wikipedia.org/wiki/File:Coal_mine_Wyoming.jpg
Let's wait 60 million years and see.