Disclaimer
If such evidence were to arise, it would not instantly overturn evolutionary theory. It would need to be scrutinised first, even replicated if possible, to show that there is no other explanation for it and that we have interpreted it correctly. Palaeontologists would first have to determine that the fossil had been correctly identified, that it was not a hoax, and that the interpretation of the fossil-bearing strata is correct. The evidence would not automatically tell us that evolution is wrong, but that there is a serious error with the theory as we currently understand it.
Predictions
One of the predictions of common descent is a nested hierarchy pattern of relatedness, with groups within groups. In evolutionary theory, groups of organisms become more derived over time and build upon the traits which their ancestors possessed. With this in mind, key traits should appear in what will appear to be an ordered fashion. For example, for humans to evolve from "lesser" animals, many features need to have already evolved, such as bilateral symmetry, a well developed head, vertebrae, the tetrapod limb set-up, mammary glands, hair, and the list goes on.
Rabbits in the Precambrian
Apparently growled by the influential evolutionary biologist J.B.S. Haldane as a response to what would make him doubt evolution, "rabbits in the Precambrian" is a phrase which is popular in discussions about the falsifiability of the theory. It is also exactly what I wish to talk about here. In the predictions I mentioned above, finding evidence which goes contrary to them would cause problems for evolution, such as finding the remains of Homo sapiens before any of those traits had evolved. We would not expect to find rabbits in the Precambrian, because rabbits are highly derived multicellular eukaryotes, more specifically animals, tetrapods, mammals and so on. Finding a multicellular organism or even more specifically an animal in the Precambrian would not be a problem (unless it was found before the evolution of eukaryotes) but finding a tetrapod or anything "higher" certainly would. Finding a tetrapod in the Cambrian or Ordovician would also cause huge problems for the theory. We could list all sorts of possible examples, which can make for quite fun thought experiments.
Fossils found out of place are termed anachronistic fossils, but simply being in the wrong place is not quite enough. These fossils need to be a specific sort of out of place fossil, such as those mentioned above. Fossils which are "out of place" could be put in a few categories, many of which would not falsify evolution.
What will not do...
Fossils which are later than expected would not falsify evolution. The fossil record documents evolution and extinction, but it does so imperfectly. Occasionally, an organism which was thought to be extinct appears later on, providing evidence that they did not go extinct at that time. For example, trilobites are exclusively Palaeozoic, so finding one in the Mesozoic would be a huge surprise, but it would not falsify evolution, as it would simply mean that they survived extinction for longer than previously thought. Claiming an organism is extinct is effectively based on an absence of fossils past the point when they were thought to go extinct and is the sort of hypothesis which cannot be empirically confirmed, but gains weight through not finding what would be necessary to falsify it.
Reworked fossils could fit with fossils which are later than expected, though there are different reasons for them. Reworked fossils were originally contained in older rocks, but have been weathered out and become part of younger rocks. This is easy to imagine occurring if you have ever been to a place where fossils are easily collected, as those loose fossils are often quite tough and could easily become part of a new sediment. Palaeontologists have ways of identifying reworked fossils most of the time. So again, these sorts of fossils would not falsify evolution.
Range extending fossils will be unlikely to falsify evolution. By this I mean fossils which extend a fossil group further back in time (or forward, but obviously that is irrelevant here). Now this is the more complicated one, as technically those fossils which can falsify evolution would fit into this category. The fossil record shows the first possible occurrences of the traits we can identify. If you find a confirmed vertebrate in older strata than anyone else has found them, then you have the earliest known occurrence of that particular trait and have extended the range, which obviously would not falsify evolution and could itself be overturned by new data. This can happen simply because the fossil record is imperfect and we simply have many more rocks to look at.
This can especially be the case with trace fossils. During the lifetime of an organism, it travels around making numerous traces but only has one body (even organisms which shed their coverings only do so a small amount of time compared to potential trails they leave). Sometimes the only record of a population is the traces they leave behind and not the bodies. We can, therefore, expect for there to be many examples of trace fossils appearing before potential causative organisms (but not much earlier). This would also happen if the environment of deposition was not conducive to preserving body fossils, but did preserve trace fossils.
So fossils which extend the range earlier in time, in order to falsify evolution, must come before traits which they are dependent on. A tetrapod being found slightly earlier than expected is simply a surprise, but a tetrapod before the evolution of jaws, or vertebrae, for example, would falsify evolution.
Fossils in the wrong environment would not falsify evolution. Fossils are occasionally found in the wrong place in the sense that they are in the wrong environment. Ankylosaurs, for example, are terrestrial animals (insofar as we are aware) and yet are often found in marine strata. Considering animals can easily float out to sea, it should be obvious why this is not a problem for evolution. We even see out of place organisms ourselves from time to time, like a beached whale, as the beach is not its habitat, it requires deeper waters. Fossils in the wrong environment are not anachronistic, even if they are sometimes puzzling.
Can this challenge be met?
If evolution is not true, then anachronistic fossils really should be the rule, not the exception. This is especially true if a global flood deposited the majority of fossils (or even just a smaller portion of them). We should not find an order consistent with evolutionary theory in such a case. Naturally, as has already been mentioned, the finding of such a fossil would not instantly overturn evolution, but it would spread ripples of doubt through the scientific community.
Anti-evolution attempts
Proponents of creationism and ID often claim that this potential falsification of evolution is dishonest and that evolutionary biologists will cobble together some sort of excuse or will ignore the data completely. Nonetheless, they provide examples from time to time which they claim fits the bill.
Rabbits fit the category of "complex non-marine multicellular eukaryotes" so some anti-evolutionists have jumped on a claim of such things in the Precambrian. See here for example. But the problem with their claim is that these fossils are not as derived as would be necessary; they are exceptionally primitive compared to even something like a jawless fish.
The relatively recent find of tetrapod trackways from around 18 million years earlier than the first tetrapod fossils is occasionally cited. For reasons already stated, we should be sceptical of this as a claimed anachronism. They were also in a different environment (one not conducive to fossilisation) to early tetrapod body fossils, which changes views on how tetrapods might have evolved. This trackway has palaeontologists asking some important questions, but it is not the sort to cast doubt on evolution. Find those trackways in the Silurian or earlier and you might have a strong case.
Other examples tend to fit into the categories I listed above which just will not do, or tend to include things such as human footprints alongside dinosaur footprints (many of which have been hoaxes or are not actually human prints). Just type something like "out of place fossils" into Google and lots of creationist claims should pop up. Follow them through though, and I am willing to bet that none are the sort which would falsify evolution.
Of course, evolution is true, and we can use it to predict what sort of fossils we can find in particular strata. There are thousands (if not millions) of people out there collecting fossils and yet they all find what we would expect if evolution were true. I find that during my own fieldwork as well; I've even joked with friends about finding an anachronistic fossil in the area I did my dissertation fieldwork. Just last night, in fact, when someone mentioned being asked if they had found any vertebrate material in their own samples, I quipped that I wanted to find some in mine, as I am studying early Cambrian rocks, which will not contain vertebrate remains. If I did find something along those lines I certainly would not suppress it, but would be able to ride the wave of publicity. Sadly, though, I will find no such thing.
