Flight has evolved among animals on four separate occassions - birds, bats, pterosaurs and winged insects - and much speculation has arisen about the circumstances of each. For only one of these clades, the birds, do we have access to a detailed fossil record demonstrating how their wings evolved; for each of the others we are still forced to rely on more indirect evidence. Winged insects are without doubt the most mysterious of the four. Vertebrate wings are instantly recognisable as modications of pre-existing forelimbs, but insect wings (at least at first glance) appear to have arisen de novo, without obvious homologues in any other arthropod group.
A long-popular hypothesis was that insect wings were derived from paranotal lobes - lateral extensions of the thorax, originally not articulated and probably used for gliding. Proposed support for the paranotal hypothesis came from the presence in a number of Palaeozoic insect groups of just such lateral projections, complete with wing-like venation, on the first segment of the thorax in addition to the actual wings on the second and third segments (contrary to many popular accounts, these insects were not 'six-winged', because the anterior lobes were fixed in place and not mobile like wings). Smaller projections in thysanurans (silverfish), the living sister group to winged insects, do allow them limited gliding ability, further supporting the proposal.
During the latter part of the last century, however, an alternative hypothesis became prominent. Kukalová-Peck (1987 and other publications) pointed out that a major problem with the paranotal theory is that the insect wing articulation is not a simple structure. Insect wings are articulated by a set of small plates surrounding the junction of the wings and the thorax. In Kukalová-Peck's view, positing the development of this articulation completely de novo strained credulity. Instead, Kukalová-Peck proposed that the wings were derived from exites, lateral branches of the legs found in crustaceans. The fossil record of marine arthropods indicates that branched legs were part of the original arthropod ground-plan and many crustaceans that retain them show modifications of the exites into alternative structures. The gills of crabs and lobsters, for instance, are modified exites. According to Kukalová-Peck's proposal, exites present in the ancestral insects were moved into a dorsal position on the thorax to give rise to the wings. As the exites would have been articulated from the start, this removed the question of how the wing articulation developed. Kukalová-Peck proposed that the exites had originally been developed as gills in aquatic ancestral insects - the two basalmost living orders of winged insects, mayflies and dragonflies, are both aquatic as nymphs (as are the stoneflies, which Kukalová-Peck regarded as the next most basal order), and mayfly nymphs have winglet-like gills on the abdomen. It was suggested that the original gills could have been transformed into wings via their development as sails for skimming across the water surface (many living stoneflies use their wings in this way). To clinch the deal, Kukalová-Peck (1987) described a number of Carboniferous insect fossils retaining exites on their legs. Strong support for an exite origin of wings came from studies of Drosophila development - many of the same genes are expressed in the development of Drosophila wings and crustacean gills, while cells involved in wing development migrate dorsally from the leg primordia (Shubin et al., 1997). By the late 1990s, the exite theory had become generally accepted.
However, the question was far from settled. The exite theory centred around an aquatic origin for winged insects, but this is doubtful. Successive sister-groups to winged insects (silverfish and archaeognathans) are terrestrial, as were the palaeodictyopteroids, one of the earliest groups of winged insects. Living winged insects other than mayflies and dragonflies form a clade called Neoptera that was probably also ancestrally terrestrial (most current researchers no longer regard stoneflies as basal among neopterans - e.g. Terry & Whiting, 2005). Adaptations to aquatic life in mayflies and dragonflies are very distinct, and the fossil and anatomical evidence suggests that these groups may have evolved aquatic nymphs independently. While fossils of winged insects are abundant by the Late Carboniferous, aquatic insects are not well-established in the fossil record until the Triassic nearly 100 million years later (Grimaldi & Engel, 2005), though a small number of aquatic nymphs have been claimed for the Permian - interpretation of these specimens is currently debated (Beckemayer & Hall, 2007). Though all the usual caveats around negative evidence still apply, the near or total absence of aquatic nymphs from Palaeozoic deposits contrasts strongly with their later abundance in Mesozoic and Cenozoic deposits, especially when one considers the presence of Carboniferous stem-dragonflies far larger than any later successor (such as the two-foot-plus-wingspan Meganeuropsis permiana) that might be expected to have had similarly robust nymphs.
Also problematic is the complete absence of thoracic leg exites in any living insect, including archaeognathans and silverfish (Update: Günter Bechly has corrected me that thoracic exites are present in archaeognathans: see comments below). It is not impossible that winged insects, silverfish and archaeognathans could have each lost their exites independently. Exites have been lost by numerous arthropod groups and their corresponding absence in arachnids and myriapods (centipedes and millipedes) suggests that the loss of exites is somehow closely connected to adoption of a terrestrial lifestyle (I think terrestrial isopods still have them). Besides, any amount of recent absences should be instantly trumped by the fossil presences recorded by Kukalová-Peck (1987). However, not all authors have accepted Kukalová-Peck's interpretations. Béthoux & Briggs (2008) examined some of the specimens from which exites had been reported (including the stem-orthopteran Gerarus) and found that the supposed 'exites' were artefacts created by overenthusiastic specimen preparation. Whether any basal insect possessed exites therefore requires confirmation - it may be difficult to support derivation of wings from exites if no exites were present for them to be derived from. Unfortunately, many of the supposedly exite-bearing specimens described by Kukalová-Peck remain in private collections and are not readily available for re-examination.
So of the currently contending explanations for the origin of insect wings, the genetic and developmental data seems to be consistent with an exite origin, but fossil and phylogenetic considerations appear more consistent with a paranotal origin. The challenge for researchers will be to reconcile this conflicting data. My personal suspicion is that some degree of genetic co-option is involved. Comparative studies on developmental genetics indicate that the evolution of new structures often involves the redeployment of pre-existing genetic pathways, and that separate lineages will often redeploy the same pathways. For instance, closely related genes are involved in the development of arthropod and vertebrate legs, despite the origins of both from legless ancestors (Shubin et al., 1997). Spider spinnerets appear developmentally homologous to abdominal legs, despite the loss of abdominal legs in arachnids a long time prior to the origin of spider spinnerets. It would be very interesting to see what the roles are in silverfish of the genes uniting insect wings and crustacean gills.
Beckemeyer, R. J., & J. D. Hall. 2007. The entomofauna of the Lower Permian fossil insect beds of Kansas and Oklahoma, USA. African Invertebrates 48 (1): 23-39.
Béthoux, O., & D. E. G. Briggs. 2008. How Gerarus lost its head: stem-group Orthoptera and Paraneoptera revisited. Systematic Entomology 33 (3): 529-547.
Grimaldi, D., & M. S. Engel. 2005. Evolution of the Insects. Cambridge University Press: New York.
Kukalová-Peck, J. 1987. New Carboniferous Diplura, Monura, and Thysanura, the hexapod ground plan, and the role of thoracic side lobes in the origin of wings (Insecta). Canadian Journal of Zoology 65: 2327-2345.
Shubin, N., C. Tabin & S. Carroll. 1997. Fossils, genes and the evolution of animal limbs. Nature 388: 639-648.