The short answer is that evolution couldn't create gills in humans. It doesn't work that way unless we're talking millions of years. However, if the humans in Waterworld had genetic engineering, it's perfectly reasonable to believe that they could create a human with gills in 50 years. The long explanation is below, along with a pretty detailed description of how evolution works.
I think one of the issues in discussing evolution is that we are conflating two different processes.
The first one is mutations. These pop up in populations at some rate -- which might be different for different species and for different populations. A population which is exposed to high levels of radiation might have a high level of mutation. However, the mutation is random. And many of the mutations will be detrimental -- even to the point of causing large numbers of failed pregnancies. (High rates of miscarriage, or of death during or shortly after pregnancy -- or of unviable eggs in an egg-laying species.)
Even currently in humans, there is actually a fairly high rate of failed pregnancies. 15% of known pregnancies result in miscarriage -- and there are probably even more that we don't know about because they happen before the woman is even aware she's pregnant. Many times, these miscarriages are because the fertilized egg doesn't develop properly, and you don't ever move from the blastocyst to a fetus. Instead, you get junk which the woman's body disposes of in a miscarriage.
The second process is selection. Mutations that are not detrimental enough to cause death will result in new beings. But the ultimate question in terms of evolution is: do these beings reproduce? And will those offspring also reproduce? In natural selection, the environment can determine whether an individual survives long enough to reproduce. Some mutations may affect this process. If a mutation makes an individual fertile for a longer period, they may have more offspring. Similarly, if a mutation ensures that the individual survives longer, that may lead to more offspring. Or if a mutation makes the individual a more attractive parent (long and colorful tails in peacocks, for example), they're more likely to mate.
However, with humans, there's a mitigating factor. We have tools, which can lead to survival of beings that might not otherwise survive. Take the Waterworld example: we have boats, and the means to build them. Therefore, in the short term, there wouldn't be any survival pressure to cause any mutation to be beneficial enough to cause a change in the population. In the longer term, however, we'd start running out of ways to fix the boats. It's a lot harder to cut down trees or mine ore if there's no dry land. At this point, the survival of those who can stay off the boats for longer may in fact start to affect the population.
There's also a question of "unnatural" selection or selective breeding. We can see that in dogs. Wolves look pretty much the same all over the world. But when humans started domesticating canines, we started choosing which males to breed with which females. Therefore, if we wanted particularly small dogs, we breed the smallest males to the smallest females, and in each generation, we continue the process. Eventually, we'll end up with toy dogs, because we're selecting for that feature. (A fascinating version of this process was used in the 1800s to create sheep and cattle with more meat.)
I think one of the most confusing aspects of evolution, however, is the idea that we can evolve a completely new organ (gills) out of nowhere. What mutations do is that they change the blueprint for what is already there. For example, they might enable a slightly higher lung capacity, which would enable people to hold their breath for longer. Over time, if this is beneficial enough, it would spread and perhaps even increase itself even more. But evolution is random. But evolution can't start from scratch. All that can happen is that the current blueprints can be adjusted. So we can start playing with lung capacity, but our genes can't randomly create something that's fully functional right from scratch. For a new organ to evolve would take FAR longer than for a minor change like being able to hold your breath longer to spread.
The only thing that matters in natural evolution is whether there is a greater likelihood of producing offspring from that mutation. If yes, then the mutation is selected for. If no, it's selected against. But most mutations have no effect. (A mutation might cause, for example, dimples to appear not just on your cheeks, but also on your elbows.) This is a completely useless mutation in terms of survival. But it might happen to get passed on simply by chance. (Our elbow-dimpled person might also happen to have lots of children.) This is evolution as it normally happens. If a mutation isn't harmful, it is just as likely to get passed on as not.
This is why in many of the more extreme animal breeds, there are other factors that tend to get passed on along with the trait that has been selected for. (For example, Thoroughbred horses, which were bred for speed, tend to have a number of problems including small heart size and bleeding from the lungs.)
The last factor to consider is a staple of science fiction -- genetic engineering. This is where we take the DNA sequence to grow X feature and place it into creature Y's DNA. Or where we go into the DNA of an organism and snip out bits that we don't like. This is currently being done in a number of areas. The most common is work being done on crops such as tomatoes or tobacco. (Just do a search for genetically modified food to see a sampling of the range of discussion on the topic.)
Depending on when Waterworld is supposed to take place, that would get my vote for the most likely origin of the gills of Kevin Costner's character. That could theoretically happen in one generation, although there would likely be a number of tries where the genes don't get expressed properly, or they don't work right, or they cause problems for some other system. (I believe the gills were in his neck, which is already chock full of other stuff like the blood vessels leading to the brain -- if the gills interfered with those, the modified baby wouldn't survive.)