DFT Functional Selection Criteria
What's up with all that magic? (A chapter formerly known as Introduction)
The hunt for for the holy grail of density functional theory (DFT) has come a long way.[1] Becke states in the introduction of the cited paper:

Density-functional theory (DFT) is a subtle, seductive, provocative business. Its basic premise, that all the intricate motions and pair correlations in a many-electron system are somehow contained in the total electron density alone, is so compelling it can drive one mad.

I really like this description, it points out why we use and need DFT, and as it also points out the flaws, that every computational chemist has to deal with: How can something with such a simple approach be correct?
Something that is often forgotten about DFT is, that in principle it is correct. It's the implementations and approximations, that make it incorrect, but usable. Becke states this in the following quote:

Let us introduce the acronym DFA at this point for “density-functional approximation.” If you attend DFT meetings, you will know that Mel Levy often needs to remind us that DFT is exact. The failures we report at meetings and in papers are not failures of DFT, but failures of DFAs.

I sometimes here that the abbreviation DFT is often used in the wrong context, since we are not talking about the theory itself any more, but about the implementations and approximations of it. One suggestion I heard was, that it should rather be used as density functional technique.
With that in mind I would like to state, that I absolutely agree with the previous answer by user1420303 and it's subsequent comment by Geoff Hutchison. Since you asked for a somewhat more practical approach, I like to offer the advice I usually give to students new in the field.
Old is bad, isn't it?
Some of the functionals are now around for about thirty years. That does not make them bad, maybe even the opposite. It shows, that they are still applicable today, giving reasonable results. One of my personal favourites is the conjunction of Becke 1988 and Perdew 1986, often abbreviated as BP86.[2] It's a pure functional which is available most modern quantum chemical packages.[3] It performs usually well enough for geometries and reasonable well for energies for simple systems, i.e. small organic molecules and reactions.
The magical functional B3LYP was one of the first hybrid functionals, and it was introduced by Gaussian's very own developers.[4] A lot of people were surprised how well it worked and it quickly became one of the most popular functionals of all time. It combines Becke's three parameter functional B3[5] with Lee, Yang and Parr's correlation functional.[6] But why are we surprised it works? The answer is quite simple, it was not fitted to anything. Frish et. al. just reworked the B3PW91 functional to use LYP instead of PW91. As a result, it heavily suffers or benefits from error compensation. Some even go as far as to say: “It is right for the wrong reasons.”[7-9] Is it a bad choice? No. It might not be the best choice, but as long as you know what you are doing and you know it is not failing for your system, it is a reasonable choice.
One functional is enough, is it?
Now that we established, that old functionals are not out of fashion, we should establish something very, very important: One is never enough.
There are a few things, where it is appropriate to do most of the work with one functional, but in these cases the observations have to be validated with other methods. Often it is best to work your way up Jacob's ladder.[10]
How do I start?
It really depends on your system and what you are looking for. You are trying to elucidate a reaction mechanism? Start with something very simple, to gain structures, many structures. Reaction mechanisms are often about the quantity of the different conformers and later about suitable initial structures for transition states. As this can get complex very fast, it's best to keep it simple. Semi-empirical methods and force fields can often shorten a long voyage. Then use something more robust for a first approach to energy barriers. I rely on BP86 for most of the heavy computing. As a modern alternative, another pure density functional, M06-L is quite a good choice, too.[11] Some of the popular quantum chemistry suites let you use density fitting procedures, which allow you to get even more out of the computer. Just to name a few, without any particular order: Gaussian, MolPro, Turbomole.
After you have developed a decent understanding of the various structures you obtained, you would probably want to take it up a notch. Now it really depends on what equipment you have at hand. How much can you afford? Ideally, more is better. At least you should check your results with a pure, a hybrid, and a meta-hybrid functional. But even that can sometimes be a stretch.[12]
If you are doing bonding analysis, elucidation of the electronic structure, conformation analysis, or you want to know more about the spectrum, you should try to use at least five different functionals, which you later also check versus ab initio approaches. Most of the times you do not have the hassle to deal with hundreds of structures, so you should focus of getting the most accurate result. As a starting point I would still use a pure functional, the worst thing that could happen is probably, that is reduces the times of subsequent optimisations. Work your way up Jacob's ladder, do what you can, take it to the max.[13]
But of course, keep in mind, that some functionals were designed for a specific purpose. You can see that in the Minnesota family of functionals. The basic one is M06-L, as previously stated a pure functional, with the sole purpose of giving fast results. M06 is probably the most robust functional in this family. It was designed for a wide range of applications and is best chosen when dealing with transition metals. M06-2X is designed for main group chemistry. It comes with somewhat built in non-covalent interactions and other features. This functional (like most other though) will fail horribly, if you have multi-reference character in your system. The M06-HF functional incorporates 100% Hartree-Fock exchange and was designed to accurately calculate time dependent DFT properties and spectra. It should be a good choice for charge transfer systems. See the original publication for a more detailed description.[14]
Then we have another popular functional: PBE.[15a] In this initial publication an exchange as well as a correlation functional was proposed, both pure density functionals, often used in conjunction.[15b] I don't know much about it's usefulness, since I prefer another quite robust variation of it: PBE0, which is a hybrid functional.[15c,d] Because of its adiabatic connection formula, it is described by the authors as a non-empirical hybrid functional.[15d]
Over the years there have been various developments, some of the are called improvement, but it often boils down to personal taste and applicability. For example, Handy and Cohen reintroduced the concept of left-right correlation into their OPTX functional and subsequently used it in combination with LYP, P86 and P91. Aparently, they work well and are now often used also as a reference for other density functionals. They went on and developed a functional analogous to B3LYP but outperforming it.[16]
But these were obviously not the only attempts. Xu and Goddard III extended the B3LYP scheme to include long range effects. They claim a good description of dipole moments, polarizabilities and accurate excitation energies.[17]
And with the last part in mind, it is also necessary to address long range corrections. Sometimes a system cannot be described accurately without them, sometimes they make the description worse. To name only one, CAM-B3LYP, which uses the coulomb attenuating method.[18] And there are a couple of more, and a couple of more to come, head on over to a similar question: What do short-range and long-range corrections mean in DFT methods?
As you can see, there is no universal choice, it depends on your budget and on the properties you are interested in. There are a couple of theoretical/ computational chemists on this platform. I like BP86 as a quick shot and answer questions relating to MO theory with it, shameless self-promotion: Rationalizing the Planarity of Formamide or Rationalising the order of reactivity of carbonyl compounds towards nucleophiles. And sometimes we have overachievers like LordStryker, that use a whole bunch of methods to make a point: Dipole moment of cis-2-butene.
So I picked a functional, what else?
You still have to pick a basis set. And even here you have to pick one that fits what you need. Since this answer is already way longer than I intended in the first place (Procrastination, yay!), I will keep it short(er).
There are a couple of universally applicable basis sets. The most famous is probably 6-31G*. This is a nice ancient basis set that is often used for its elegance and simplicity. Explaining how it was built is easier, than for other basis sets. I personally prefer the Ahlrichs basis set def2-SVP, as it comes with a pre-defined auxiliary basis set suitable for density fitting (even in Gaussian).[19]
Worth mentioning is the Dunning basis set family cc-pVDZ, cc-pVTZ, ... . They were specifically designed to be used in correlated molecular calculations. They have been reworked and improved after its initial publication, to fit them to modern computational standards.[20]
The range of suitable basis sets is large, most of them are available through the basis set exchange portal for a variety of QC programs.
Sometimes an effective core potential can be used to reduce computational cost and is worth considering.
*Sigh* What else?
When you are done with that, consider dispersion corrections. The easiest way is to pick a functional that has already implemented this, but this is quite dependent on the program of you choice (although the main ones should have this by now, it's not something brand new). However, the standalone DFT-D3 program by Stefan Grimme's group can be obtained from his website.[21]
Still reading? Read more! (A chapter formerly known as Notes and References)

Axel D. Becke, J. Chem. Phys., 2014, 140, 18A301.
(a) A. D. Becke, Phys. Rev. A, 1988, 38, 3098-3100. (b) John P. Perdew, Phys. Rev. B, 1986, 33, 8822-8824.
Unfortunately this functional is not always implemented in the same way, although the differences are pretty small. It basically boils down as to which VWN variation is used in the local spin density approximation term. Also see S. H. Vosko, L. Wilk, and M. Nusair, Can. J. Phys., 1980, 58 (8), 1200-1211.
P. J. Stephens, F. J. Devlin, C. F. Chabalowski, and M. J. Frisch, J. Phys. Chem., 1994, 98 (45), 11623–11627.
Axel D. Becke, J. Chem. Phys., 1993, 93, 5648.
C. Lee, W. Yang, and R. G. Parr, Phys. Rev. B, 1988, 37, 785–789
Unfortunately the B3LYP functional suffers from the same problems that are mentioned in [3].
The failures of B3LYP are known and often well documented. Here are a few recent papers, but there are many, many more. (a) Holger Kruse, Lars Goerigk, and Stefan Grimme, J. Org. Chem., 2012, 77 (23), 10824–10834. (b) Joachim Paier, Martijn Marsman and Georg Kresse, J. Chem. Phys., 2007, 127, 024103. (c) Igor Ying Zhang, Jianming Wu and Xin Xu, Chem. Commun., 2010, 46, 3057-3070. (pdf via researchgate.net)
Just my two cents, that I am hiding in the footnotes: “Pretty please do not make this your first choice.”
John P. Perdew and Karla Schmidt, AIP Conf. Proc., 2001, 577, 1. (pdf via molphys.org)
Yan Zhao and Donald G. Truhlar, J. Chem. Phys., 2006, 125, 194101.
Note, that not always full recomputations of geometries are necessary for all different functionals you apply. Often single point energies can tell you quite much how good your original model performs. Keep the computations to what you can afford.
Don't use an overkill of methods, if you already have five functionals agreeing with each other and possibly with an MP2 calculation, you are pretty much done. What can the use of another five functionals tell you more?
Y. Zhao, N.E. Schultz, and D.G. Truhlar, Theor. Chem. Account, 2008, 120, 215–241.
(a) John P. Perdew, Kieron Burke, and Matthias Ernzerhof, Phys. Rev. Lett., 1996, 77, 3865. (b) The exchange functional was revised in Matthias Ernzerhof and John P. Perdew, J. Chem. Phys., 1998, 109, 3313. (c) Carlo Adamo and Vincenzo Barone, J. Chem. Phys., 1999, 110, 6158. (d) Kieron Burke, Matthias Ernzerhof, and John P. Perdew, Chem. Phys. Lett., 1997, 265, 115-120.
(a) N. C. Handy and A. J. Cohen, Mol. Phys., 2001, 99, 403-12. (b) A. J. Cohen and N. C. Handy, Mol. Phys., 2001, 99 607-15.
X. Xu and W. A. Goddard III, Proc. Natl. Acad. Sci. USA, 2004, 101, 2673-77.
T. Yanai, D. P. Tew, and N. C. Handy, Chem. Phys. Lett., 2004, 393, 51-57.
(a) Florian Weigend and Reinhart Ahlrichs, Phys. Chem. Chem. Phys., 2005, 7, 3297-3305. (b) Florian Weigend, Phys. Chem. Chem. Phys., 2006, 8, 1057-1065.
The point where the use of more basis functions does not effect the calculation. For the correlation consistent basis sets, see a comment by Ernest R. Davidson, Chem. Phys. Rev., 1996, 260, 514-518 and references therein. Also see Thom H. Dunning Jr, J. Chem. Phys., 1989, 90, 1007 as the original source.
DFT-D3 Website; Stefan Grimme, Jens Antony, Stephan Ehrlich, and Helge Krieg,
J. Chem. Phys., 2010, 132, 154104.
Have fun and good luck!