And the state fossil of Minnesota is...

...nothing. Despite the map on "List of U.S. state fossils" [note, 2018/2/22: this has since been fixed], Minnesota does not have an official state fossil. There was a push to draft the giant beaver into this position, but the rodent fell short. The immediate political reason for its failure can be grasped from its scientific name: Castoroides ohioensis. Should the state fossil of Minnesota refer to another state? Certainly not!

Sorry, pal...

In hindsight, it's probably best that C. ohioensis fell short, for the reason given above and for reasons of state dignity. After all, we are talking about a giant beaver. Still, it is somewhat odd that Minnesota doesn't have a state fossil when the great majority of states do. A couple of factors that may have contributed to this: Minnesota doesn't have one singular highlight fossil, but rather a great diversity of forms; and it's pretty lean in terms of large vertebrates. We've got lots and lots of small filter-feeding invertebrates, but almost no dinosaurs, and almost no mammals except for the very end of the Quaternary. When the Ice Ages came, other places got frolicking mammoths, sloths, saber-toothed cats, and so on. We got the ice. There's a decent selection of mammoths south of the Minnesota/Mississippi river system, but Alaska, Nebraska, South Carolina, and Washington already have mammoths as their state fossils (plus mastodons for Michigan). So, what other options are there? Let's toss some out there for some enterprising person to investigate.

Some ground rules: I'm going to avoid fossils that other states have used. The fossil should be reasonably representative of the state, visually interesting, and not too difficult to explain. It should not require the use of magnification to appreciate. Its scientific name should not include a location outside of Minnesota. Finally, per discussion with other volunteers at the Science Museum of Minnesota, "no bryozoans". I think this is kind of unfair, and it knocks out Prasopora, which is quite common in the state and reasonably endearing for a bryozoan, but I'll adhere.

Honorable mention: there are a number of visually distinct and abundant Ordovician invertebrates that one could throw out, but most of them lack a "hook". For example, I like Rauffella as something which is visually interesting and unarguably a common fossil in the state, but at the end of the day it's a worm burrow. We are swarming in crinoid columnals, brachiopods, and trilobite fragments, but there isn't really one standout, and Kentucky already did general brachiopods. Cystoids lose points because of their rarity, the unappealing name, their somewhat disturbing appearance, and the amount of explanation they'd require.

My candidates

The hash slab

Pro: Hash slabs are undeniably common in Minnesota; other states (Kentucky and brachiopods, Georgia and shark teeth) have already used generic fossils, so there's some precedent; they are representative of the types of fossils that Minnesota is best known for; a diverse and well-prepared hash plate is visually appealing.
Con: The coward's way out.

An edrioasteroid

Foerstediscus splendens, from Minnesota (photo of USNM specimen from Wikimedia Commons).

Pro: Nobody else is using an edrioasteroid; we've got some gorgeous specimens, such as the Foerstediscus above.
Con: They're rare and tiny; explaining what an edrioasteroid is takes more work than most of my other choices.

One of our big orthoconic nautiloids

Pro: Our Ordovician nautiloids are reasonably common; they are much larger than most of our other fossils; easier to interpret and explain than some other choices; people find cephalopods fascinating.
Con: They seem a little white-bread, and not entirely representative, but I can't think of anything that would really harm their case except for trying to pick one particular genus or species.

A receptaculitid, like Fisherites oweni

Pro: Receptaculitids are large and visually interesting fossils; they are also reasonably common.
Con: They don't lend themselves to explanation; although visually interesting, they are otherwise kind of dull in that they just sat there in life.

An extinct bison, like Bison occidentalis

Pro: One of the most frequently encountered fossil mammal in the state; most accessible of the selected choices; it's a good solid American symbol.
Con: Bison are not all that exotic, and it may be difficult to get people to think of bison in terms of fossils; it would be nice to have that one great specimen as a rallying point; taxonomy is also an issue.

I think if you were to put these five choices to people, the bison or the nautiloid would win, although the receptaculitid and edrioasteroid may put in surprisingly strong performances based on their interesting appearances.