Faits:
A. Par contrat du 24 septembre 2001, A._ a cédé aux époux H.X._ et F.X._ l'usage d'un appartement de trois pièces et demie à ... (VD) moyennant un loyer de 1'450 fr. par mois.
L'immeuble a été acquis le 7 janvier 2002 par Y._, qui est ainsi devenue la bailleresse.
Par lettre du 2 octobre 2002, les locataires se sont plaints pour la première fois du bruit causé par le moteur de l'ascenseur, dont la cage jouxte leur appartement. Cet ascenseur date de la construction de l'immeuble en 1983.
Aucun accord n'ayant été trouvé, les locataires, considérant que la chose louée était défectueuse, ont consigné le loyer dès le mois de septembre 2005.
B. Le 29 septembre 2005, les locataires ont saisi la Commission de conciliation en matière de baux et loyers du district de Morges, demandant l'exécution des travaux nécessaires pour éliminer le bruit excessif, ainsi qu'une diminution de loyer de 20 % dès le début du bail, le 1er octobre 2001.
La cause n'ayant pas été conciliée, les locataires ont saisi le Tribunal des baux et loyers, lequel, par jugement du 26 octobre 2007 rendu sans frais ni dépens, a rejeté la demande et libéré les loyers consignés en faveur de la bailleresse.
Les locataires ont recouru contre ce jugement à la Chambre des recours du Tribunal cantonal vaudois. Devant cette autorité, ils ont conclu en dernier lieu à ce qu'il soit constaté que la consignation de loyer est fondée, à ce que les travaux nécessaires soient ordonnés pour éliminer définitivement le bruit excessif de l'ascenseur, à ce que les loyers demeurent consignés jusqu'à l'exécution parfaite des travaux, à ce qu'une réduction de loyer de 20 % leur soit accordée depuis le 1er octobre 2001 jusqu'au 31 décembre 2006, soit 18'270 fr., à ce que la bailleresse soit condamnée à leur payer la somme de 18'270 fr. avec intérêts à 5 % l'an dès le 1er octobre 2005, ainsi qu'une somme de 234 fr.05 (correspondant aux frais d'une expertise privée) avec intérêts à 5 % dès le 28 mars 2006.
Par arrêt du 13 février 2009, la Chambre des recours a confirmé le jugement attaqué et mis les frais à la charge des recourants. La cour cantonale est parvenue à la conclusion que la chose louée n'était pas défectueuse, parce que la nuisance sonore n'excédait pas les limites de tolérance. La cour cantonale a retenu en particulier les faits suivants: un rapport de l'entreprise chargée de l'entretien de l'ascenseur daté du 9 mai 2003 indique que le bruit de cet engin s'entend dans l'appartement des demandeurs, toutefois, un employé de l'entreprise, entendu comme témoin, a déclaré que le bruit de cet ascenseur était faible par rapport à celui d'autres installations; une voisine, également entendue comme témoin, qui habite le même type d'appartement mais à un étage différent, a déclaré qu'elle avait été dérangée par le bruit de l'ascenseur à son arrivée pendant une quinzaine de jours, puis qu'elle s'y était habituée et que l'ascenseur ne l'empêchait pas de dormir; le Tribunal des baux s'est rendu sur place et a procédé à des essais, sans toutefois entendre de bruit dérangeant dans l'appartement loué, alors même qu'il y est resté durant près de deux heures; selon un rapport du 11 décembre 2007 d'un service officiel (SEVEN), le bruit perçu peut atteindre 40 dB(A) alors que le maximum devrait être en principe de 33 dB(A), mais qu'aucune règle n'est violée en raison de l'année de construction de l'immeuble; l'opinion de ce service, selon laquelle ce bruit pourrait être dérangeant durant la nuit, a été écartée au vu de l'ensemble des autres éléments de preuve recueillis.
C. Ayant reçu cet arrêt le 1er mai 2009, H.X._ et F.X._ ont déposé dans un bureau de poste suisse, le mardi 2 juin 2009 (suivant la Pentecôte) un recours en matière civile au Tribunal fédéral. Invoquant une violation des articles 8 CC, 274d al. 3 CO ainsi qu'une mauvaise application de la notion de défaut, ils concluent, avec suite de frais et dépens, à l'annulation de l'arrêt attaqué et reprennent leurs conclusions sur le fond; subsidiairement, ils demandent le renvoi de la cause à l'autorité précédente. L'effet suspensif sollicité a été accordé par ordonnance présidentielle du 25 juin 2009.
L'intimée a conclu au rejet du recours avec suite de frais et dépens.

Considérant en droit:
1. 1.1 Interjeté par les parties qui ont succombé dans leurs conclusions condamnatoires (<ref-law>) et dirigé contre un jugement final (<ref-law>) rendu en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>) dans une affaire pécuniaire dont la valeur litigieuse atteint le seuil de 15'000 fr. requis en matière de droit du bail (<ref-law>), le recours est en principe recevable, puisqu'il a été déposé dans le délai (art. 45 al. 1 et 100 al. 1 LTF) et la forme (<ref-law>) prévus par la loi.
1.2 Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Sous réserve de la violation d'un droit constitutionnel ainsi que d'une question relevant du droit cantonal ou intercantonal (cf. <ref-law>), le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.1 p. 104). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (<ref-law>), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent, lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 1.1 p. 105).
1.3 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire : <ref-ruling> consid. 8.1 p. 153, 135 III 127 consid. 1.5 p. 130 - ou en violation du droit au sens de l'<ref-law> (<ref-law>).
La partie recourante qui entend s'écarter des constatations de l'autorité précédente doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (cf. <ref-ruling> consid. 1.4 p. 140). Elle ne peut demander une correction de l'état de fait que si celle-ci est susceptible d'influer sur le sort de la cause (<ref-law>). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
1.4 Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (<ref-law>). Toute conclusion nouvelle est irrecevable (<ref-law>).
2. 2.1 Les recourants se plaignent tout d'abord d'une violation de l'<ref-law>.
Pour tous les litiges fondés sur le droit privé fédéral, cette disposition, en l'absence d'une règle spéciale instituant une présomption, répartit le fardeau de la preuve et détermine, sur cette base, laquelle des parties doit assumer les conséquences de l'échec de la preuve (<ref-ruling> consid. 3.1 p. 323; <ref-ruling> consid. 2.6 p. 24). En l'espèce, les locataires ont accepté la chose louée lorsque celle-ci a été mise à leur disposition le 1er octobre 2001 (leur première réclamation date du 2 octobre 2002); dès lors qu'ils sont entrés en possession sans réserve, il faut en déduire que la bailleresse a fourni sa prestation; il incombe dès lors aux locataires de prouver les faits dont on peut déduire l'existence du défaut qu'ils invoquent pour en déduire des droits (PETER HIGI, Zürcher Kommentar, n° 42 ad <ref-law>). La cour cantonale n'a donc pas violé le droit fédéral en considérant que le fardeau de la preuve incombait aux recourants. Au demeurant, la règle sur le fardeau de la preuve cesse d'être applicable dès le moment où le juge est parvenu à une conviction sur la base de l'appréciation des preuves (<ref-ruling> consid. 3.4 p. 634; <ref-ruling> consid. 2b/aa p. 277); Or, en l'espèce, la cour cantonale est parvenue à la conviction qu'il n'y avait pas de bruit excessif (arrêt attaqué p. 11).
Il a été également déduit de l'<ref-law> un droit à la preuve et à la contre-preuve, à la condition qu'il s'agisse d'établir un fait pertinent contesté, qui n'est pas déjà prouvé, par une mesure probatoire adéquate, laquelle a été régulièrement offerte selon les règles de la procédure applicable; il n'y a pas de violation de l'<ref-law> si une mesure probatoire est refusée à la suite d'une appréciation anticipée des preuves (ATF <ref-ruling> consid. 2.6 p. 24 s. et les arrêts cités). En l'espèce, la cour cantonale a statué sur la base des témoignages recueillis, des pièces produites (notamment un rapport officiel sur la mesure du bruit), ainsi que sur un transport sur place effectué par le Tribunal des baux. L'instruction apparaît donc très complète et on ne voit pas en quoi les recourants auraient été entravés dans la possibilité d'apporter leurs preuves en temps utile. Il n'y a donc pas trace non plus d'une violation du droit à la preuve déduite de l'<ref-law>.
Il faut rappeler que l'<ref-law> ne prescrit pas quelles sont les mesures probatoires qui doivent être ordonnées (<ref-ruling> consid. 2a p. 522), ni comment le juge doit apprécier les preuves et sur quelle base il peut parvenir à une conviction (<ref-ruling> consid. 2a p. 522). L'appréciation des preuves ne pourrait être revue que sous l'angle de l'arbitraire (art. 9 Cst.).
2.2 Les recourants se plaignent également d'une violation de l'<ref-law>.
Cette disposition prévoit que le juge établit d'office les faits et apprécie librement les preuves, mais elle ajoute que les parties sont tenues de lui présenter toutes les pièces nécessaires à l'appréciation du litige. Elle institue une maxime inquisitoire sociale, qui ne signifie pas que le juge doit instruire d'office le litige lorsqu'une partie renonce à expliquer sa position; le juge doit seulement interroger les parties, et les informer de leur devoir de collaboration et de production des preuves; l'initiative du juge ne va pas au-delà de l'invitation faite aux parties de mentionner les preuves et de les présenter (<ref-ruling> consid. 4a p. 238 s). Selon la jurisprudence constante, cette maxime ne permet pas d'étendre à bien plaire l'administration des preuves et d'exiger toutes les mesures probatoires concevables (<ref-ruling> consid. 4a p. 239; arrêt 4C.199/2000 du 21 décembre 2000 consid. 2a, publié in SJ 2001 I p. 278; arrêt 4C.161/1997 du 18 mai 1998 consid. 2a; arrêt 4C.458/1995 du 23 avril 1996 consid. 2a, publié en traduction in Cahiers du bail [CdB] 1996 p. 113 ss). Ainsi, l'<ref-law> ne permet pas plus que l'<ref-law> de compléter ad libitum l'administration des preuves. Sous cet angle également, on ne voit pas que l'arrêt cantonal viole le droit fédéral.
Par ailleurs, il a déjà été jugé que l'<ref-law> ne prescrit pas au juge comment il doit apprécier les moyens de preuve qui lui sont soumis (arrêt 4C.264/2002 du 25 août 2003 consid. 4.2, publié in SJ 2004 I p. 93). Dans la mesure où les recourants se plaignent de la manière dont les preuves ont été administrées, cette argumentation est impropre à démontrer une violation de l'<ref-law>. En conséquence, on ne voit pas non plus que cette disposition ait été violée.
2.3 On peut se demander si les recourants ne demandent pas un complètement de l'état de fait, sur la base de l'<ref-law>, lorsqu'ils font valoir que la cour cantonale n'a pas pris en compte le rapport de l'entreprise chargée d'entretenir l'ascenseur qui indique que le bruit de cette installation est perceptible dans l'appartement des recourants. Il n'y a cependant pas lieu de compléter l'état de fait, puisque la constatation en cause figure de manière explicite à la page 2 in fine de l'arrêt attaqué. De surcroît, ce point de fait ne serait pas propre à influencer la décision attaquée (<ref-law>), puisque la question pertinente n'est pas de savoir si l'on entend l'ascenseur, mais si celui-ci provoque un bruit dépassant le seuil de tolérance. Il n'y a donc pas lieu de corriger l'état de fait cantonal et le raisonnement juridique doit être conduit sur la base de celui-ci (<ref-law>).
3. 3.1 Les recourants soutiennent que la cour cantonale a procédé à une appréciation arbitraire des preuves et qu'elle a méconnu la notion juridique de défaut.
Savoir quel est le bruit que provoque le fonctionnement de l'ascenseur dans l'appartement occupé par les recourants est une question de fait; dire si ce bruit constitue un défaut de la chose louée est une question de droit, puisqu'il s'agit de qualifier les faits en fonction d'une notion juridique, à savoir la notion de défaut.
S'agissant de l'établissement des faits, les recourants soutiennent que la cour cantonale a procédé à une appréciation arbitraire des preuves. S'agissant d'un grief constitutionnel (art. 9 Cst.), le Tribunal fédéral ne peut l'examiner que dans la mesure où il a été suffisamment motivé (<ref-law>). Or, les recourants ne font que reprendre les constatations figurant dans l'arrêt cantonal, en minimisant les points qui leur sont défavorables et en insistant sur ceux qui leur sont favorables, ainsi qu'en opposant leur propre appréciation des preuves à celle de la cour cantonale. Une telle argumentation est impropre à démontrer l'arbitraire. Il faut rappeler que le juge dispose d'un large pouvoir d'appréciation dans l'examen des preuves recueillies; il n'y a arbitraire que si l'autorité ne prend pas en compte, sans aucune raison sérieuse, un élément de preuve propre à modifier la décision, lorsqu'elle se trompe manifestement sur son sens et sa portée, ou encore lorsque, en se fondant sur les éléments recueillis, elle en tire des constatations insoutenables (<ref-ruling> consid. 2.1 p. 9). Les recourants s'efforcent seulement de montrer comment on pourrait motiver une décision différente, mais ils ne démontrent pas en quoi, sur l'un ou l'autre des points de fait, la position prise par la cour cantonale serait manifestement insoutenable. Il n'y a donc pas lieu d'entrer en matière, faute d'une motivation suffisante.
Avant d'aborder la question juridique de savoir s'il y a ou non défaut de la chose louée, il faut apporter une précision. Les recourants invoquent un prétendu défaut qui existait dès leur entrée en jouissance de l'appartement; ils sont cependant entrés en possession des locaux sans réserve et n'ont invoqué le défaut que beaucoup plus tard; dans une telle situation, les locataires ne peuvent invoquer que les prétentions qu'ils pourraient faire valoir en cas de défaut survenant en cours de bail (<ref-law>). Les droits des locataires sont donc régis par les art. 259a à 259i CO (art. 258 al. 2 et 3 CO).
3.2 Faute de définition légale, la notion de défaut - qui relève du droit fédéral - doit être rapprochée de l'état approprié à l'usage pour lequel la chose a été louée (<ref-law>); elle suppose la comparaison entre l'état réel de la chose et l'état convenu; il y a ainsi défaut lorsque la chose ne présente pas une qualité que le bailleur avait promise ou lorsqu'elle ne présente pas une qualité sur laquelle le locataire pouvait légitimement compter en se référant à l'état approprié à l'usage convenu (arrêt 4C.387/2004 du 17 mars 2005 consid. 2.1; arrêt 4C.97/2003 du 28 octobre 2003 consid. 3.1; arrêt 4C.81/1997 du 26 janvier 1998 consid. 3a; DAVID LACHAT, Le bail à loyer, 2008, n° 9.1.1, p. 216, nos 9.1.3 et 9.1.4, p. 218 et s.; PIERRE TERCIER/PASCAL G. FAVRE, Les contrats spéciaux, 2009, n° 2061, p. 304). Il n'est pas nécessaire que le bailleur soit en faute ou que le défaut soit réparable (SVIT-Kommentar Mietrecht, éd. 2008, n° 16 ad Vorbem. Art. 258-259i CO; LACHAT, op. cit., nos 9.2.3 et 9.2.5, p. 224). Le défaut de la chose louée est une notion relative; son existence dépendra des circonstances du cas particulier; il convient de prendre en compte notamment la destination de l'objet loué, l'âge et le type de la construction, ainsi que le montant du loyer (PIERRE WESSNER, Le bail à loyer et les nuisances causées par des tiers en droit privé, in 12ème Séminaire sur le droit du bail, 2002, p. 23 s.; HIGI, op. cit., n° 28 ad <ref-law>; arrêt 4C.387/2004 du 17 mars 2005 consid. 2.1).
S'agissant plus précisément du bruit, le locataire ne saurait s'attendre, sauf promesse spéciale (inexistante en l'espèce), à un silence absolu. Il est plus ou moins inévitable que des bruits provenant de l'extérieur puissent être perçus à l'intérieur d'un logement. Que l'on entende un bruit dans un appartement ne suffit pas pour conclure à l'existence d'un défaut. On ne sort des limites de ce à quoi le locataire devait s'attendre que si le bruit, compte tenu de sa durée, de son intensité et du moment où il se manifeste, dépasse un certain seuil et entrave l'usage normal de la chose louée, par exemple en perturbant le sommeil. La jurisprudence a déjà eu l'occasion de souligner que la nuisance sonore devait dépasser les limites que le locataire devait supporter en fonction de l'usage normal de la chose louée; elle a cité l'exemple de voisins particulièrement bruyants ou d'un immeuble dont l'isolation phonique est exceptionnellement mauvaise; elle a également relevé que des nuisances sonores propres à perturber le sommeil dans un logement d'habitation était excessives (arrêt 4C.368/2004 du 21 février 2005 consid. 4.1 et les références citées, publié in MietRecht Aktuel [MRA] 2005 p. 196 ss.). La notion de seuil de tolérance implique évidemment qu'un certain pouvoir d'appréciation est laissé au juge du fait. Pour dire quels sont les bruits avec lesquels le locataire devait normalement compter (et qui ne constituent donc pas un défaut par rapport à l'usage convenu), il faut tenir compte du lieu de situation de l'immeuble, de la qualité de son aménagement, de son degré de vétusté, ainsi que des activités exercées dans l'immeuble et du comportement normalement prévisible des autres occupants.
L'arrêt attaqué, dans ses développements théoriques, ne contient rien qui conduise à penser que la cour cantonale a mal interprété la notion juridique de défaut de la chose louée.
3.3 Il reste à examiner si la cour cantonale a violé le droit fédéral dans sa qualification juridique des faits retenus.
Les recourants, qui n'ont certainement pas loué l'appartement sans l'avoir vu, devaient s'attendre à un certain bruit provenant de l'ascenseur, puisque leur appartement jouxte directement la cage de cette installation. L'entreprise chargée de l'entretien de l'ascenseur a certes relevé que le bruit s'entendait dans l'appartement des recourants, mais son employé a aussi déclaré que le bruit de cette installation état plutôt faible par rapport à d'autres, ce qui donne à penser - sans arbitraire - qu'il n'y a ici rien d'extraordinaire. Une voisine occupant un appartement semblable a déclaré qu'elle avait été dérangée au début (ce qui confirme que l'ascenseur est bruyant), mais elle a aussi déclaré qu'elle s'était habituée après une quinzaine de jours et que le fonctionnement de l'ascenseur ne la dérangeait pas dans son sommeil. On ne peut pas déduire de cette déclaration que le seuil de tolérance soit dépassé. Quant aux mesures du bruit effectuées par un service officiel, elles ont abouti à la conclusion qu'aucune norme applicable n'a été violée. Certes, ce service a estimé que le bruit était "dérangeant", ce dont les recourants font grand cas; savoir si le seuil de tolérance est dépassé est cependant une question de droit qui doit être tranchée par le juge, et non par un service technique. Le Tribunal des baux s'est rendu sur place et il y est resté longuement, en procédant notamment à des essais; cette opinion suffit à contrebalancer l'avis divergent du service technique. Aux arguments présentés par la cour cantonale, on peut en ajouter un autre: les recourants sont entrés dans les locaux le 1er octobre 2001 et ils ont attendu une année pour se plaindre par lettre du 2 octobre 2002. L'absence prolongée de réaction après l'entrée en jouissance est un indice sérieux que la chose louée est dans un état qui correspond à ce que le locataire avait en vue au moment de la conclusion du contrat (LACHAT, op. cit., n° 9.1.3, p. 218). Si l'on songe que l'ascenseur fonctionne tous les jours et, dans une mesure réduite, pendant la nuit, l'absence de réaction pendant une année est difficilement compatible avec la notion d'un défaut qui restreint l'usage pour lequel la chose a été louée (<ref-law>). Si l'on porte une appréciation sur l'ensemble de ces éléments, on ne peut pas conclure que la cour cantonale ait violé le droit fédéral en estimant que le seuil de tolérance n'avait pas été dépassé.
En conséquence, le recours doit être rejeté.
4. Les frais judiciaires et les dépens sont mis à la charge de la partie qui succombe (art. 66 al . 1 et 5, art. 68 al. 1, 2 et 4 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires fixés à 2'000 fr. sont mis solidairement à la charge des recourants.
3. Les recourants verseront solidairement à l'intimée une indemnité de 2'500 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Chambre des recours du Tribunal cantonal du canton de Vaud.
Lausanne, le 31 juillet 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Klett Crittin