This argument is actually not a creationist one, but originates with Karl Popper. He claims that evolution is unfalsifiable, hence unscientific (from which does not follow that it is invalid, contrary to the node's title!). Popper also rejected the scientific status of Freud's theories of the psyche, for what he claimed was the same reason.

First, it should be noted that while Popper's view that scientific theories are judged on their falsifiability, it is by no means universally accepted. The 20th century did have other philosophers of science, and they weren't all students of Popper!

But the question of falsifiability is still an interesting one, even if one doesn't accept it as the sole determinant of being a scientific theory. And at its most abstract, natural selection is indeed unfalsifiable. It describes the (quasi-) stable state of a system (the ecology), when that system is so large as to be a singleton, and is already known to be in its quasi-stable state. In plainer English, this means that you're looking at a system shaped by Evolution, and that this is the only system available for you to examine. Thus, you cannot see Evolution in action, for the simple reason that you cannot see the ecology's adaption to environmental changes over "reasonable" timescales.

Note, however, that this rejection does not apply to the existence of intra-species variation, but only to natural selection on that variation. The existence of variation is easily established empirically; this is much less than ymelup's claim above about genetics.

But we still don't have to reject natural selection. First of all, it is the only possible theory which makes sense in the presence of random natural variation: If there is such variation, and environmental changes occur, wouldn't you expect to see "survival of the fittest" types of variation? It's the only logical possibility! So naturally, it is unfalsifiable -- one might as well try to falsify statements like "1+1=2".

And on smaller scales, we don't have to wait so long, so we can observe natural selection. The best examples are of course bacteria. Bacteria can exchange genetic material directly (with plasmids), which is a lot faster than sex. And their life cycle is anyway much faster than ours. And their environment changes drastically. Guess what? Hospitals are manufacturing antibiotic-resistant strains of bacteria! How do they do it? My guess is this: Some strains of bacteria are resistant to some antibiotics. Normally, whenever a gene conferring such resistance transfers to another bacterium, it is almost certain to confer no advantage to that organism (since this antibiotic is rare, especially in the environment of a bacterium of another strain). So the incidence of that gene remains low. But in a hospital environment the antibiotic is extremely common, so having resistance confers a spectacular advantage. Sure enough, pathogenic bacteria are incorporating these genes. Of course, it's not clear that the original variation was random in origin (how do you prove something is random, anyway?). But all "neutral" variations (i.e. those not conferring any advantage) appear random. And natural selection explains why "positive" variations (i.e. those conferring some advantage) concentrate so much. And while random variation has been observed, directed variation has never been.

To sum up: The existence of random genetic variation is the only part evolution that might be open to the "argument by unfalsifiability". It is falsifiable, of course, but only in the presence of large amounts of directed variation; but it's not open to direct proof. We've never seen directed mutation (even if it exists, you'd expect it to be very rare; unfalsifiability, anyone?). And in the presence of random genetic variation, natural selection is inevitable, and a clear logical consequence. All scientific theories contain such a logical "kernel" (for physics, e.g., it is mathematics), which is unfalsifiable in and of itself.

As a theory, Evolution is safe.