What mutations are needed for a particular trait (e.g. wings) to arise?

You're right that random mutation alone doesn't cut it. That's where natural selection comes in. Natural selection works upon the random mutations to produce strings of beneficial mutations. You see, evolution works not on individuals, but on populations. If one member of a population gains a beneficial mutation, I'll call it A, over a few generations a large proportion of the population might have that mutation, especially if the mutation helped the first animal with the mutation have more successful offspring than its peers.So then you have a population full of A-mutants. It's likely they'll continue to mutate as they reproduce, so if one animal out of the population has a second beneficial mutation, B, the population might end up full of animals with both A and B mutations. The AB-mutants continue like this, and eventually you have ABC-mutants. This process can repeat again and again, and the population can split up, and the environment can change, and before you know it the original population has split up into a bunch of groups that are all different from what their ancestors were like.We get a distorted view of the probabilities of these events because the fossil record is limited by various factors, like the rarity of fossilization, while modern animals all look different because they are the tips of the branches on the evolutionary tree. We don't see too many of the dead ends deep in the evolutionary tree (though we've found a few, like pterosaurs) and we also fail to see that the way things are now is only one way, out of a practically infinite number of possibilities, that things could have turned out.

A number of flying or gliding animals have been mentioned in this thread - insects, birds, pterosaurs, flying squirrels, and so on. One that has not been mentioned is Sharovipteryx mirabilis, a reptile which had a membrane across its hind legs that allowed it to glide. This makes it the only known animal that used a flight system dominated by its hind legs.Animal News - Science and Zoology Articles

If I have a hundred dice, and I roll them all, there are a large number of possibilities. 6^100, to be exact. But even though this number is very large, that doesn't mean that it is impossible to get any particular combination. If I roll all the dice, I have to get some combination, even if that combination is extrememly unlikely.Another way to think about it is like this: If I paint a picture, there is a virtually infinite number of ways I could make my brush strokes, so there is a virtually infinite number of different paintings I could paint. But that doesn't mean it is impossible to paint a painting.I don't see why mutation and natural selection are not likely to produce anything useful, in your opinion. I think we have to agree on a definition of "beneficial mutation". I would define it as one which increases an organism's biological fitness, which is the ability of that organism to reproduce effectively. There many kinds of beneficial mutations - they could protect against disease, or help an animal evade predators so it can live long enough to reproduce, or the mutation can increase the number of offspring, or even lower the number of offspring, if these offspring are then more likely to grow up and reproduce. It could also do something more subtle, like allow for a particular nutrient to be absorbed in a new way, so the mutant is less likely to die of a deficiency in this nutrient.In the case of birds, mutations in genes which affect scale growth could have resulted in downy feathers, which kept dinosaurs warm. These may have only been present when the dinosaur was young. Other types of feather, such as contour feathers, may not have started out as particularly aerodynamic. They may have been much smaller in relation to the whole animal, and they may have covered only the forelimbs. These could be useful in mating displays, in much the same way birds of paradise have elaborate displays which mainly show off their feathers. They could have grown longer, as peacock tails have, into something that improved agility on the ground and even could have been used for gliding. From there, gliding developed into powered flight which we see in modern birds.This is an outline based somewhat on my speculation, but experiments have indicated that feathers are modified scales, and a number of fossil species have been found with impressions of feathers. Some could fly, some could not. Caudipteryx had long feathers on its forelimbs and tail, but does not appear to have been able to fly. These feathers may have been used to attract mates or for some other purpose. There also seem to be some dead ends - for example, Microraptor gui appears to have had four wings. Its fore and hind limbs had long feathers. You can think of this as another way birds could have turned out, with four wings instead of two, but for some reason, this didn't work out.