I think that is a good question. What really are the most important elements of paleontology that the general public should understand? I took a shot at coming up with a list of key concepts, based on experiences with teaching paleontology and historical geology and with less-formally structured outreach to the public. I have offered this list (cross posted at the Sauropod Vertebrae Picture of the Week, Dave Hone’s Archosaur Musings, and Superoceras blogs) as a way for it to reach a wider audience. That this is Darwin Week makes it even more appropriate, as we should use this occasion to encourage a better understanding of the changes of Earth and Life through Time for the public at large.
Much as I might like to think otherwise, the specific details of the hindlimb function of Tyrannosaurus rex or the pneumatic features of brachiosaurid vertebrae really are not the most important elements of the field. Understanding and appreciating the nitty gritty details of the phylogeny and anatomy of any particular branch of the Tree of Life are not really necessary for everyone to know, any more than we would regard detailed knowledge of bacterial biochemistry or the partitioning of minerals in a magma chamber to be significant general knowledge. (Indeed, these latter two items are actually far more critical for human society than any specific aspect of paleontology, and so from a certain point of view really more important for people to know than the History of Life.)
That said, all human societies and many individuals have wondered about where we have come from and how the world came to be the way it is. This is, in my opinion, the greatest contribution of paleontology: it gives us the Story of Earth and Life, and especially our own story.
I have divided this list into two sections. The first is a list of general topics of paleontology, touching on the main elements of geology that someone would need to know for fossils to make any sense. The second is the more specific list of key points in the history of life.
(NOTE: as the idea of this list is that it should be aimed at the general public, I have tried to avoid technical terminology where possible.)

GENERAL:

• That rocks are produced by various factors (erosion à sedimentation; metamorphism; volcanic activity; etc.)
• That rocks did not form at a single moment in time, but instead have been and continue to be generated throughout the history of the planet.
• That fossils are remains of organisms or traces of their behavior recorded in those rocks.
• That rocks (and the organisms that made the fossils) can be thousands, millions, or even billions of years old.
• That the species discovered as fossils, and the communities of organisms at each place and time, are different from the same in the modern world and from each other.
• That despite these differences that there is continuity between life in the past and life in the present: this continuity is a record of the evolution of life.
• That we can use fossils, in conjunction with anatomical, molecular, and developmental data of living forms, to reconstruct the evolutionary pattern of life through time.
• That fossils are incomplete remains of once-living things, and that in order to reconstruct how the organisms that produced them actually lived, we can:
• Document their anatomy (both gross external and with the use of CT scanning internal), and compare them to the anatomy of living creatures in order to estimate their function;
• Examine their chemical composition, which can reveal aspects of their biochemistry;
• Examine their microstructure to estimate patterns of growth;
• Model their biomechanical functions using computers and other engineering techniques;
• Investigate their footprints, burrows, and other traces to reveal the motion and other actions of the species while they were alive;
• And collect information of the various species that lived together in order to reconstruct past communities.
• However, with all that, fossils are necessarily incomplete, and there will always be information about past life which we might very much want to know, but which has been forever lost. Accepting this is very important when working with paleontology.
• That environments of the past were different from the present.
• That there have been episodes of time when major fractions of the living world were extinguished in a very short period of time: such data could not be known without the fossil record.
• That entire branches of the tree of life have perished (sometimes in these mass extinction events, sometimes more gradually).
• That certain modes of life (reef formers, fast-swimming marine predators, large-bodied terrestrial browsers, etc.) have been occupied by very different groups of organisms at different periods of Earth History.
• That every living species, and every living individual, has a common ancestor with all other species and individuals at some point in the History of Life.

SPECIFIC:
Honestly, despite the fact the specific issues about specific parts of the Tree of Life are the ones that paleontologists, the news media, the average citizen, etc., are more concerned with, they really are much less significant for the general public to know than the points above. Sadly, documentary companies and the like keep on forgetting that, and keep on forgetting that a lot of the public does not know the above points.
Really, in the big picture, the distinction between dinosaurs, pterosaurs, and crurotarsans are trivialities compared to a basic understanding that the fossil record is our document of Life’s history and Earth’s changes.
Summarizing the key points of the history of life over nearly 4 billion years of evolutionary history is a big task. After all, there is a tendency to focus on the spectacular and sensationalized rather than the ordinary and humdrum. As Stephen Jay Gould and others often remarked, from a purely objective external standpoint we have always lived in the Age of Bacteria, and the changing panoply of animals and plants during the last half-billion years have only been superficial changes.
But the question wasn’t “what should a dispassionate outsider regard as the modal aspect of the History of Life?”; it was “What should everyone know about paleontology?” Since we are terrestrial mammals of the latest Cenozoic, we have a natural interest in events on the land and during the most recent parts of Earth History. That is a fair bias: it does focus on who WE are and where WE come from.

That said, here is a list of key concepts in the history of life. Other researchers might pick other moments, and not include some that I have here. Still, I believe most such lists would have many of the same key points within them.

• Life first developed in the seas, and for nearly all of its history was confined there.
• For most of Life’s history, organisms were single-celled only. (And today, most of the diversity remains single-celled).
• The evolution of photosynthesis was a critical event in the history of Earth and Life; living things were able to affect the planet and its chemistry on a global scale.
• Multicellular life evolved independently several times.
• Early animals were all marine forms.
• The major groups of animals diverged from each other before they had the ability to make complex hard parts.
• About 540 million years ago, the ability to make hard parts became possible across a wide swath of the animal tree of life, and a much better fossil record happened.
• Plants colonized land in a series of stages and adaptations. This transformed the surface of the land, and allowed for animals of various groups to follow afterwards.
• For the first 100 million years or so of skeletonized animals, our own group (the vertebrates) were relatively rare and primarily suspension feeders. The evolution of jaws allowed our group to greatly diversify, and from that point onward vertebrates of some form or other have remained apex predators in most marine environments.
• Complex forests of plants (mostly related to small swampland plants of today’s world) covered wide regions of the lowlands of the Carboniferous.
• Burial of this vegetation before it could decay led to the formation of much of the coal that powered the Industrial Revolution and continues to power the modern world.
• While most of the coal swamp plants required a moist ground surface on which to propagate, one branch evolved a method of reproduction using a seed. This adaptation allowed them to colonize the interiors, and seed plants have long since become the dominant form of land plant.
• In the coal swamps, one group of arthropods (the insects) evolved the ability to fly. From this point onward insects were to be among the most common and diverse land animals.
• Early terrestrial vertebrates were often competent at moving around on land as adults, but typically had to go back to the water in order to reproduce. In the coal swamps one branch of these animals evolved a specialized egg that allowed them to reproduce on land, and thus avoid this “tadpole” stage.
• These new terrestrial vertebrates—the amniotes—diversified into many forms. Some included the ancestors of modern mammals; others the ancestors of today’s reptiles (including birds).
• A tremendous extinction event, the largest in the age of animals, devastated the world about 252 million years ago. Caused by the effects and side-effects of tremendous volcanoes, it radically altered the composition of both marine and terrestrial communities.
• In the time after this Permo-Triassic extinction, reptiles (and especially a branch that includes the ancestors of crocodilians and dinosaurs) diversified and became ecologically dominant in most medium- to large-sized niches.
• During the Triassic many of the distinctive lineages of the modern terrestrial world (including turtles, mammals, crocodile-like forms, lizard-like forms, etc.) appeared. Other groups that would be very important in the Mesozoic but would later disappear (such as pterosaurs and (in the seas) ichthyosaurs and plesiosaurs) evolved at this time.
• Dinosaurs were initially a minor component of these Triassic communities. Only the tall, long-necked sauropodomorphs were ecologically diverse during this time among the various dinosaur branches. However, a mass extinction event at the end of the Triassic (essentially the Permo-Triassic extinction in miniature) allowed for the dinosaurs to diversify as their competitors had vanished.
• During the Jurassic, dinosaurs diversified. Some grew to tremendous size; some evolved spectacular armor; some become the largest carnivorous land animals the world had seen by this point. Among smaller carnivorous dinosaurs, an insulating covering of feathers had evolved to cover the body (possibly from a more ancient form shared by all dinosaurs). Among the feathered dinosaurs were the ancestors of the birds.
• Other terrestrial groups such as pterosaurs, crocodile-ancestors, mammals, and insects continued to diversify into new habits.
• During the Jurassic and (especially) the Cretaceous, a major transformation of marine life occurred. Green-algae phytoplankton were displaced by red-algae phytoplankton (which continue to dominate modern marine ecosystems). A wide variety of new predators—advanced sharks and rays, teleost fish, predatory snails, crustaceans with powerful claws, specialized echinoids, etc.—appeared, and the sessile surface-dwelling suspension feeders that dominated the shallow marine communities since the Ordovician became far rarer. Instead, more mobile, swimming, or burrowing forms became more common.
• During the Cretaceous one group of land-plants evolved flowers and fruit and thus tied their reproduction very closely with animals. Although not immediately ecologically dominant, this type of plants would eventually come to be the major land plant group.
• The impact of a giant asteroid—coupled with other major on-going environmental changes—brought an end to the Mesozoic. Most large-bodied groups on land and sea, and many smaller bodied forms, disappeared. The only surviving dinosaurs were toothless birds.
• The beginning of the Cenozoic saw the establishment of mammals as the dominant group of large-bodied terrestrial vertebrates. Early on mammals colonized both the sea and the air as well.
• During its beginning the Cenozoic world was warm and wet, much like the Cretaceous. However, a number of changes of the position of the continents and the rise of mountain ranges caused the climates to cool and dry.
• As the world cooled and dried, great grasslands developed (first in South America, and later nearly all other continents).
• Various groups of animals adapted to the new grassland conditions. Herbivorous mammals became swift runners with deep-crowned teeth, often living in herds for protection. Mammalian predators became swifter as well, some becoming pack hunters.
• Other new plant communities evolved, and new animal communities which inhabited them. The rise of modern meadows (dominated by daisy-related plants and grasses) saw the diversification of mouse-and-rat type rodents, many frogs and toads, advanced snakes, songbirds, etc.
• A group of arboreal mammals with very big brains, complex social communities, and gripping hands—the primates—produced many forms. In Africa one branch of these evolved to live at mixed forest-grassland margins, and from this branch evolved some who became fully upright and moved out into the grasslands.
• This group of primates retained and advanced the ability to use stone tools that its forest-dwelling ancestors already had. Many branches evolved, and some developed even larger brains and more complex tools. It is from among these that the ancestors of modern humans and other close relatives evolved, and eventually spread out from Africa to other regions of the planet.
• About 2.6 million years ago a number of factors led to ice age conditions, where glaciers advanced and retreated. Various groups of animals evolved adaptations for these new cold climates.
• The early humans managed to colonize much of the planet; shortly after their arrival into new worlds, nearly all the large-bodied native species disappeared.
• At some point before the common ancestor of all modern humans spread across the planet, the ability to have very complex symbolic language evolved. This led to many, many technological and cultural diversifications which changed much faster than the biology of the humans themselves.
• In western Asia and northern Africa (and eventually in other regions), modern humans developed techniques to grow food under controlled circumstances, leading to true agriculture. (Other cultures are known to have independently evolved proto-agricultural techniques).
• This Neolithic revolution allowed for the development of more settled communities, specialization of individual skills within a community (including soldiers, metallurgists, potters, priests, rulers, and with the rise of writing, scribes).
• From this point we begin to get a written record, and so the historians can take up the story…