It has been argued that the small, simple, everyday examples of evolution do not involve new information. This argument is sometimes correct. For example, the famous black moths did not contain new genetic information.
In order to make room for new information, there have to be types of mutation which make a genome larger. It turns out that several kinds of mutation do this, notably duplication and polyploidy.
If a bacteria becomes penicillin-resistant, it really does contain new information. We know this because researchers have now got to the point where they have read out (sequenced) every last bit of the DNA in some bacteria. This means that it's possible to do before-and-after measurements.
Here's an example. Take a nice fresh culture dish, and place a single bacteria on it. A colony will grow. This is "before".
Take one bacteria from "before", and start a new culture with it. After the culture is well-started, add some antibiotic. Somewhere in the culture, there may be a mutant who is resistant to the antibiotic. If there isn't such a mutant, they all die. In that case, start over. If necessary, you can encourage mutation, maybe with some radioactivity.
Eventually, you will find such a mutant. You will know it's there because it reproduces, and your culture dish will contain a living colony instead of a dead one. This is "after".
Now get the DNA sequences of "before" and "after". Several researchers have done just this, and the DNA sequences have been published. It is definitely the case that "after" can have new genetic information, which is not present in "before".
In the above example, a beneficial mutation allowed the bacteria to survive a negative thing. It is equally easy to get a mutation that allows a positive thing. For example, give your colony a huge supply of some food which they cannot eat. Eventually some mutant will be able to eat the food, and will have a great many descendants. Then wipe out the normals (by withdrawing the normal food) and you have an "after" colony. As one researcher said:
Here's a tested recipe for isolating successful mutations... Grow a batch culture of Salmonella typhimurium strain SK2979 at 37 deg. C on Neidhardt's MOPS-based minimal medium with 0.4% glycerol as the carbon source and 10 mM L-aspartate as the nitrogen source. Dilute and subculture for several days. L-aspartate fast growing mutants will take over the culture in something under 3 days. These typically have a doubling time of 60 minutes on asparate, compared to about 120 minutes for the parental, wild-type strain.Even better, starting with the fast-growing strain, one can easily isolate secondary mutation(s) which permit growth on aspartate as the sole carbon and nitrogen source -- which the parental strain simply cannot do. This demonstrates how cumulative mutations can arise.
Basically, techniques involving the natural occurrence of spontaneous, beneficial mutations are commonly used by bacterial geneticists.
The above is from a 1995 Usenet posting by Tim Ikeda (timi@mendel.berkeley.edu), UC-Berkeley Plant Biology.
Some Creationists have argued that these beneficial mutations involve simplification of the bacteria, so that some aspect attacked by the antibiotic is no longer present. That idea would rarely explain the ability to consume a new food, since that usually requires new chemical pathways. Before-and-after genetic analysis says that the "simplification" idea is just not always the case. For example, the malaria parasite has become resistant to chloroquine, by learning to make a new protein. Other examples are known from studies of pesticide resistant insects.
It is also illogical that "simplification" always be the case. A mutation is due to a completely random malfunction of the genetic mechanisms. There is simply nothing to prevent a bacteria from occasionally acquiring increased complexity. If the more complex genetic material happens to be useful, then the bacteria has by definition acquired information. It has "learned" what works. As one scientist put it, "evolution is a transfer of information from the environment to the genome."
You might wonder how a change could fail to be damaging. If all of a bacteria's genetic information is useful, then any change must have removed something useful. This is half-true, because bacteria do indeed run a tight ship. ("Higher" creatures are different, and carry around lots of genetic junk.) However, the chemical mechanisms which use genes do not really understand the idea of dosage. That is, if a creature needs twice as much of one chemical as another, there is no way to tell the mechanism "make twice as much". (I'm simplifying. Actually, hemoglobin has "enhancers" and "promoters".) The obvious trick for solving this problem is to simply have two copies of the gene. Therefore, creatures carry around two or more copies of some genes. If one copy is changed by a mutation, the creature can get along fairly well on the other one(s).
Gene duplication is a fairly common mutation. Having an extra copy doesn't "cost" much, so a creature with such a mutation isn't at any great disadvantage. Extra copies are actually fairly common in the genetic material of "higher" creatures. And of course a mutation that changes an extra copy is not the same problem as a mutation that changes an only copy.
Some idea of what geneticists are up to can be obtained by poking around at BIONET. Or, if you read Usenet newsgroups such as bionet.journals.contents, you can see what's being published in, say, Journal of Molecular Evolution or Molecular & General Genetics.