Sometimes it's hard to remember, but the early Paleozoic wasn't a complete water world. We've seen a bit of that up in Taylors Falls, where the sea surrounded basaltic islands during the late Cambrian. A less obvious example is at the contact of the Shakopee Formation and St. Peter Sandstone, which represents a few million years of exposure and erosion between marine cycles. The unusual thickness of the Decorah Shale in the Twin Cities has been interpreted as a result of nearby landmasses supplying sediment (the Transcontinental Arch, running northeast–southwest through the state). Land in the early Paleozoic gets a rap as an uninhabited wasteland (in fact, absence of land plants is sometimes put forward as one of the conditions necessary for the great sand sheets of the Cambrian into the Ordovician), and it's not like we have a lot of big showy fossils to dispute this perception. There are some hints, though.
Our oldest records of actual multicellular land plants are dominated by spores, which is not too surprising given that spores stand a much better chance of preservation than your typical terrestrial non-vascular plant (mosses, liverworts, etc.). These show that plants were colonizing the land by at least ~470 Ma, about the time of the Shakopee–St. Peter hiatus, and that vascular plants were around by the end of the Ordovician. It's been thought that these first land plants were not major influences on their environment, lacking roots and such, but modern mosses are no slouches at chemical weathering, and weathering from early plants may be implicated in Ordovician glacial cycles (quite a bit of debate there; see for example Lenton et al. 2012, Quirk et al. 2015, Porada et al. 2016). Early plants also appear to have given atmospheric oxygen the last kick toward the modern level, from the Ordovician into the Early Devonian, by causing more carbon burial (Lenton et al. 2016).
If plants were abundant enough to do these things, we ought to be able to find some body fossils to go with their spores. Where to look? In a recent study, Cardona-Correa et al. (2016) went to our old friend the Platteville, focusing on an outcrop in Dane County, southern Wisconsin. The formation and location were chosen for specific reasons. First, the Platteville was chosen because of the presence of fungal microfossils in the slightly younger Guttenburg Formation (roughly equivalent to the lower Decorah of the Twin Cities) (Redecker et al. 2000). These fungal microfossils appear to represent glomalean fungi, which are often symbiotic with plants today. The location is about 50 km (30 mi) from the ancient Baraboo Range, which was probably somewhat more imposing 455 million years ago when it was one of the few terrestrial areas in the region. That "terrestrial" bit is the important part, because the closer to shore, the more likely you could get transported plant remains.
Cardona-Correa et al. dissolved about 13 lb (6 kg) of rock in hydrochloric acid to retrieve organic microfossils. Among the foraminifera (basically "amoebas with shells") and acritarchs (a true "wastebasket" of organic microfossils that defy further classification) were a handful, fewer than 20, of multicellular fragments. Most of these fragments were polygonal arrays of cells in sheets, with a few flattened cylinders of cells. Cardona-Correa et al. compared these to the leaves and stems of peat moss, respectively (recognizing that moss leaves and stems aren't quite the same as the leaves and stems of vascular plants). If correct, not only do these fossils help to put a "face" to the early spore-producers, as well as confirm the general timing of plant groups diverging from each other as estimated through molecular clocks, but they are also evidence for very early peatlands.
These aren't the kind of fossils you're liable to stumble across, unless you too have access to facilities for treating samples as well as a good microscope and a lot of patience (13 pounds of rock for <20 fragments on the order of a few hundred microns across), but if they can be found once, it should only be a matter of time and effort to find more.
Cardona-Correa, C., M. J. Piotrowski, J. J. Knack, R. E. Kodner, D. H. Geary, and L. E. Graham. 2016. Peat moss–like vegetative remains from Ordovician carbonates. International Journal of Plant Sciences 177(6):523–538.
Lenton, T. M., M. Crouch, M. Johnson, N. Pires, and L. Dolan. 2012. First plants cooled the Ordovician. Nature Geoscience 5:86–89.
Lenton, T. M., T. W.Dahl, S. J. Daines, B. J. W. Mills, K. Ozaki, M. R. Saltzman, and P. Porada. 2016. Earliest land plants created modern levels of atmospheric oxygen. Proceedings of the National Academy of Sciences of the United States of America 113(35):9704–9709.
Porada, P., T. M. Lenton, A. Pohl, B. Weber, L. Mander, Y. Donnadieu, C. Beer, U. Pöschl, and A. Kleidon. 2016. High potential for weathering and climate effects of non-vascular vegetation in the Late Ordovician. Nature Communications 7, article 12113. doi:10.1038/ncomms12113.
Quirk, J. J. R. Leake, D. A. Johnson, L. L. Taylor, L. Saccone, and D. J. Beerling. 2015. Constraining the role of early land plants in Palaeozoic weathering and global cooling. Proceedings of the Royal Society B 282(1813):20151115. doi
Redecker, D., R. Kodner, and L. E. Graham. 2000. Glomalean fungi from the Ordovician. Science 289(5486):1920–1921.