While the evolution of birds and feathers posed a seemingly unsolvable riddle to Charles Darwin (because neither were the sufficient technologies nor the database or the fossil record (of today) available to him) we now have the knowledge to correctly identify the class aves (modern birds) as avian theropods and also understand the evolution of feathers!
It may seem impropable from a superficial point of view at first, but feathers indeed evolved from reptilian scales (to be more precise: A specialised tpye of scales called scutate scales). If you ever had the opportunity to touch a feather and a piece of reptile skin, you may have noticed the similar feel of both materials. At least 6 different stages in the evolution of feathers have been identified so far:
1. Protofeathers - a simple hollow shaft lacking the branching structures of the more complex feather types
2. Downfeathers - multiple extensions branching from the central shaft
3. Axial plume feathers - similar to the down-type but further structured
4. Contour feathers - well structured symmetrical feathers that shape the outline of the body and cover the more plumulaceous feathers
5. Symmetrical feathers - fully structured feathers that may have served for a multidude of purposes (see below)
6. Asymmetric feathers - commonly known as "flight feathers" in modern avian theropods (birds)
While there exists broad consensus that the first three types of feathers evolved for insulatory purposes, many different purposes have been proposed for the three latter feather-types:
1. Display and sexual selection (Mayr, 1960)
2. Shielding from heat (Regal, 1975)
3. Insect trapping (Ostrom, 1979)
4. Water repellency (Dyck, 1985)
5. Shading while hunting (Tullborn & Hamley, 1985)
6. Aerodynamic purposes (Heilmann, 1927 ; Savile, 1962 ; Feduccia, 1980)
7. Brooding (Hopp & Orsen, 2004)
Since hypotheses 2 - 5 have been dismissed as main driving forces behind the evolution of feathers I would like to say a few words about the remaining three. These will reflect my personal views about those hypotheses, however I will try to reference where possible.
Display and sexual selection: This hypothesis is based on the inference that non-avian theropods propably showed mating behaviours resembling those of modern avian theropods. Since both extant archosauria and aves show such behaviours the inference has a high propability (first order inference). Flapping of wings is a mating behaviour present in some modern avian theropods. Non-avian theropods may have showed similar behaviour. Tetrao tetrix (Black Grouse) for example shows a mating behaviour where those males able to perform the highest jumps over the longest period of time get selected by the females for reproduction. If similar patterns of behaviour were present in theropods this may explain how possession of longer, more complex feathers may have led to selection for reproduction and thus the evolution of asymmetrical feathers since possession of the latter would favour individuals in mating contests. However, this is solely based on inference and (to my knowledge) no fossil record exists that would allow to be interpreted as evidence for the inference. Moreover our knowledge concerning sexual dimorphism (sex-related differences in animal morphology) in non-avian theropods is rather scanty at this time which adds to keeping thoughts concerning possible mating behaviours for these animals on the speculative side. Moreover studies of theropod forelimb mechanics indicate that theropod forelimb movement was very restricted in terms of flapping and thus makes a very strong point against this hypothesis (Carpenter, 2002).
Aerodynamic purposes: This hypothesis explains the evolution of feathers in connection with flight (trees down). Small theropods may have discovered and explored trees as possible habitats. The cooler (micro-) climate of their new surroundings may have led to the evolution of protofeathers for insulatory purposes in the first place as those (hypothetical) arboreal theropods became more adapted towards their "leaping from branch to branch" lifestyle. Development of down- and contour- feathers enabled them to become "parachuters". The next stage (symmetrical feathers) would be represented by animals adapted for gliding from tree to tree and finally lead to the development of fully asymmetrical flight feathers of modern type. The evolution of large, avian-like brains in advanced theropods speaks clearly in favour of this hypothesis when seen in context with a three-dimensional arboreal lifestyle! While this hypothesis may look very likely from a strictly intuitive point of view, it actually is rather problematic:
1. A huge time-gap (about 30 million years) exists between those known fossils possibly representing the early stages and Archaeopteryx (which may have been already adapted for gliding). However, teeth bearing a velociraptorine serration morphology are known from the middle jurassic and thus the discovery of further fossil material may close this gap.
2. Except for Microraptoria, no fossil record in support of an arboreal lifestyle in early maniraptorans exists (to my knowledge).
3. The most likely candidates for the early stages of this scenario (Dromaeosauridae) were all cursorial (ground dwelling runners) adapted animals.
4. The stiffened tails of the Dromaeosauridae and many other maniraptorans are not favourable for serving as a "5th limb" as seen in many arboreal animals today.
Brooding: This hypothesis explains the evolution of feathers in terms of avian brooding and hatchling-attendance behaviours. Modern avian theropods use their wings and the feathers of their wings for brooding and to give protection to hatchlings. Since non-avian theropods developed feathers as body insulation, they may have also used them for brooding purposes. More complex feather types would have provided additional durability against contact with the ground while brooding and hatchlings accidentally stepping on them when being protected by the adult. Theropod forelimb biomechanics also appears to agree with the movements required for this type of behaviour. While this hypothesis may look "far fetched" from an intuitive point of view, it actually has a lot of points speaking for it:
1. Brooding and parental care behaviours are known in both extant avian theropods and archosaurs (first order inference).
2. Fossil record exists that theropods were brooding in an avian-like manner (Oviraptor philoceratops).
3. Plausible canditates for feathers and brooding behaviour are maniraptorans from the early to middle Jurassic. Since fossil record of maniraptorans from both periods is present no time gap occurs.
4. Since no further adaptions besides those we know already to have occured (elongation of forelimbs, folding of the arms similar to that of modern avian theropods, possession of feathery integument) are required, theropods had all the long years of the early and middle Jurassic in order to develop asymmetrical feathers before they were first applied for flight.
For a fully elaborate version of the last two hypotheses please see the respective chapters in "Feathered Dragons" (full reference can be found on the index-page under credits).

Problematic aspects of the theropod - bird transition:
Of the many arguements presented in the "great debate" over the origin of modern avian theropods, only a single one stood well until recently:
Feduccia (2002a, b, 2003) and Galis et al. (2003, 2005) claimed that from observations in modern avian theropods embryo's fingers it could be proven that modern avian theropods were not the descendants of non-avain theropods.
In the publications these scientists reported their observation that in avian theropod embryos five fingers can be identified in the early stages and fingers 1 and 5 are lost during the further developmental stages of the embryo. This would have meant that the "finger count" for avian theropods would have been 2, 3, 4 and not 1, 2, 3 as would be expected in animals that evolved from non-avian theropods. However, Vargas and Fallon (2005) demonstrated that the assumption that modern avian theropod's finger identity is 2, 3, 4 was based on an artifact of observation and morphological and molecular evidence clearly indicates that modern avian theropods possess fingers 1, 2, 3 as did their non-avian ancestors.
"The dinosaurs are not extinct. The colorful and successful diversity of the living birds is a continuing expression of basic dinosaur biology." (R. T. Bakker "Dinosaur renaissance" 1975)

Finally: "God created Liaoning because He hated creationists." Dr. Paul Willis