The most obvious problem with this claim is that what is meant by "information" is never actually defined by creationists. Do they mean new genetic "instructions" - new and different genes being added to a genome? Do they mean new physical DNA being added to expand a genome? "Information" is quite a vague term, and can mean a multitude of things.
I would assume, however, in most cases, "information" refers to new genes being "added" to a genome, since genes ultimately supply the "information" or "instructions" an organism needs for body plan organization, carrying out metabolic processes, growth and development. And if the claim really is that there are never new genes added to a genome, then the claim is blatantly false.
Adding new "information" to the genome is actually quite simple and very common in the natural world (that is, outside the laboratory). It's a little process called gene duplication.
I won't get into all the nitty gritty details about the various ways that gene duplication occurs, because they're not all that relevant to the topic at hand, but common causes of gene duplication are homologous recombination, retrotransposition, or simply errors in DNA replication (the DNA Polymerase slipping back along the DNA strand, for instance). In either instance, the result is an extra copy of a gene is present in the genome.
A great example of gene duplication are the human globin genes. We do not simply have one gene for "hemoglobin"; rather, humans have a variety of hemoglobin genes: α-hemoglobin, and β-hemoglobin are the two expressed the most in adults, with ε- and ζ-hemoglobin expressed in the embryo, and γ-hemoglobin expressed during all stages of development. It should be of no surprise that all of the hemoglobin genes, despite being expressed at different times during the human life cycle and having slightly different functions, are all very related. The various forms of hemoglobin have arisen through gene duplications. According to Ross Hardison1,
"In the distant past, some ancestral - probably single-celled - organism had one hemoglobin gene, and therefore one kind of hemoglobin protein. But at some point, this gene was duplicated, so that each of the resulting daughter cells carried two identical copies of the ancestral hemoglobin gene. Gradually, during successive cell divisions, small variations in the sequence of nucleotides - the subunits that make up a gene - started to appear. In this way, the two genes that started out identical acquired sequence differences and later, functional differences. It is quite likely that additional hemoglobin genes were acquired the same way, by gene duplication followed by modifications in the nucleotide sequence."
I can already hear the cries of the creationists. "But," they proclaim, "this doesn't show evolution at all, for the different hemoglobin genes are still all the same kind!" (Oh how I hate that dreaded "kind" word). This is where gene duplications can get interesting. Once a gene duplication occurs, you have an extra copy of whatever gene that's been duplicated in your genome. This essentially works like a "backup" copy of the gene. Since a lot of mutations are deleterious (but not most mutations, as the creationists would have you believe), then having this backup copy gives a clear advantage - one copy is free to be mutated without the organism encountering any deleterious effects. These duplicated genes gain mutations at a faster rather than other genes, since potentially disastrous mutations in them won't kill the organism, allowing them to be passed on to future generations and sustain even more mutations (compared to a non-duplicated gene, where a disastrous mutation kills the organism, so neutrally and unmutated copies are what get passed on to future generations).
What does this mean? It means that the gene now has the potential to take on new functions, different regulation, etc. In essence, the duplicated copy has the potential to become an entirely new gene - one that gives an entirely new function - such as being able to metabolise a new food substrate, break down toxic compounds or grow larger and more quickly. New genetic "information" has been added to the genome.
It amazes me that the "no new genetic info" claim is still such a common one among creationists. Gene duplication as a major player driving evolution has been accepted by the scientific community for the better part of the last 100 years2. Indeed, Susumu Ohno had claimed back in 1967 that gene duplication is the single most important factor in evolution3. The reality is that new genetic "information" is added to genomes - yours, mine, every living organism's - quite easily and quite commonly.
EDIT: And it can get even easier. Prokaryotic organisms, like bacteria (and even some eukaryotes like amoeba) can take up bits of exogenous DNA (that is, DNA that is simply floating around in their environment), adding "new information" to their repertoire almost instantly!
EDIT #2: Looks as if some simple multicellular organisms like bdelloid rotifers are also able to take up foreign DNA from their environment.
------------------------------------
1. Hardison, R. (1999) . "The Evolution of Hemoglobin" American Scientist 87.2: p126
2. Taylor, JS. & Raes, J. (2004). "Duplication and Divergence: The Evolution of New Genes and Old Ideas" Annual Review of Genetics 9: 615-643
3. Ohno S. 1967. Sex Chromosomes and Sex-linked Genes. Berlin: Springler-Verlag. 192 pp.