When you hear talk of evidence for evolution, the first thing that frequently comes to mind for most people are fossils. The fossil record has one important, unique characteristic: it is our only actual glimpse into the past where common descent is proposed to have taken place. As such it provides invaluable evidence for common descent. The fossil record is not "complete" (fossilization is a rare event, so this is to be expected), but there is still a wealth of fossil information.
What Is the Fossil Record?
If you look at the fossil record, you find a succession of organisms that suggest a history of incremental development from one species to another. You see very simple organisms at first and then new, more complex organisms appearing over time. The characteristics of newer organisms frequently appear to be modified forms of characteristics of older organisms.
This succession of life forms, from simpler to more complex, showing relationships between new life forms and those that preceded them, is strong inferential evidence of evolution. There are gaps in the fossil record and some unusual occurrences, such as what is commonly called the Cambrian explosion, but the overall picture created by the fossil record is one of consistent, incremental development.
At the same time, the fossil record is not in any way, shape, or form suggestive of the idea of sudden generation of all life as it appears now, nor does it support transformationism. There is no way to look at the fossil record and interpret the evidence as pointing towards anything other than evolution — despite all the gaps in record and in our understanding, evolution and common descent are the only conclusions that are supported by the full spectrum of evidence.
This is very important when considering inferential evidence because inferential evidence can always, in theory, be challenged on its interpretation: why interpret the evidence as inferring one thing rather than another? Such a challenge is only reasonable, though, when one has stronger alternative — an alternative that not only explains the evidence better than what's being challenged, but which preferably also explains other evidence that the first explanation does not.
We don't have this when with any form of creationism. For all their insistence that evolution is only a "faith" because so much evidence is "merely" inferential, they are unable to present an alternative that explains all that inferential evidence better than evolution — or even anywhere close to evolution. Inferential evidence isn't as strong as direct evidence, but it's treated as sufficient in most cases when enough evidence exists and especially when there are no reasonable alternatives.
Fossils & Converging Evidence
That the fossil record in general suggests evolution is certainly an important piece of evidence, but it becomes even more telling when it is combined with other evidence for evolution. For example, the fossil record is consistent in terms of biogeography — and if evolution is true, we would expect that the fossil record would be in harmony with current biogeography, the phylogenetic tree, and the knowledge of ancient geography suggested by plate tectonics. In fact, some finds, such as fossil remains of marsupials in Antarctica are strongly supportive of evolution, given that Antarctica, South America and Australia were once part of the same continent.
If evolution did happen, then you would expect not just that the fossil record would show a succession of organisms as described above, but that the succession seen in the record would be compatible with that derived by looking at currently living creatures. For example, when examining the anatomy and biochemistry of living species, it appears that the general order of development for the major types of vertebrate animals was fish -> amphibians -> reptiles -> mammals. If current species developed as a result of common descent then the fossil record should show the same order of development.
In fact, the fossil record does show the same order of development. In general, the fossil record is consistent with the developmental order suggested by looking at the characteristics of living species. As such it represents another independent piece of evidence for common descent, and a very significant one since the fossil record is a window to the past.
Fossils & Scientific Predictions
We should also be able to make some predictions and retrodictions as to what we would expect to see in the fossil record. If common descent occurred, then the organisms found in the fossil record should generally conform to the phylogenetic tree — the nodes on the tree at which a split occurs represent common ancestors of the organisms on the new branches of the tree.
We would predict that we could find organisms in the fossil record showing characteristics that are intermediate in nature between the different organisms that evolved from it and from the organisms from which it evolved. For example, the standard tree suggests that birds are most closely related to reptiles, so we would predict that we could find fossils which show a mix of bird and reptile characteristics. Fossilized organisms that posses intermediate characteristics are called transitional fossils.
Exactly these sort of fossils have been found.
We would also expect that we would not find fossils showing intermediate characteristics between organisms that are not closely related. For example, we would not expect to see fossils that appear to be intermediates between birds and mammals or between fish and mammals. Again, the record is consistent.