Faits: A. Par contrat du 14 décembre 1995, La Fondation Y._ a cédé à H.X._ et F.X._ (les locataires), dès le 1er juillet 1997 et pour une durée indéterminée, l'usage d'un appartement de cinq pièces dans un immeuble sis à Onex (Genève) moyennant un loyer annuel fixé initialement à 7'344 fr. Le bail indique que le loyer est régi par la loi fédérale du 4 octobre 1974 encourageant la construction et l'accession à la propriété de logements (LCAP; RS 843) et par son ordonnance d'exécution du 30 novembre 1981 (OLCAP; RS 843.1). Les locataires étaient informés qu'il y aurait une augmentation de loyer de 6 % tous les deux ans afin de rembourser les avances effectuées sur vingt-cinq ans par la Confédération dans le but de maintenir des loyers bas. Par la suite, le loyer a été régulièrement augmenté, à chaque fois de 6 %. Les hausses étaient motivées par "l'adaptation au plan des loyers de l'Office fédéral du logement (OFL)". Le 9 mars 2005, le loyer a été augmenté à 10'344 fr. l'an avec effet au 1er juillet 2005, soit une hausse de 15 %. Le pli de la gérance indiquait que cette majoration correspondait à "une adaptation partielle du loyer à la liste des loyers LCAP" selon la demande de l'OFL; il était précisé qu'un recours pouvait être interjeté devant cet office. Les locataires se sont opposés à cette hausse auprès de l'Office fédéral du logement; ils ont conclu à ce que le loyer ne soit pas augmenté de plus de 6 %, comme cela avait été prévu contractuellement. Par décision du 10 janvier 2008, l'OFL a déclaré que la hausse notifiée le 9 mars 2005 n'était pas abusive et qu'elle était notamment conforme aux art. 45 LCAP et 17 OLCAP, s'agissant d'une hausse extraordinaire; il a même indiqué que le loyer contesté restait en-deçà de la limite maximale autorisée par ledit office. Les locataires n'ont pas recouru contre cette décision auprès du Tribunal administratif fédéral. Ils se sont par ailleurs acquittés du loyer litigieux dès son entrée en vigueur. B. Le 7 septembre 2007, les locataires ont saisi la Commission de conciliation en matière de baux et loyers du canton de Genève, demandant qu'il soit constaté que l'augmentation de loyer ne pouvait pas dépasser 6 % tous les deux ans et que le loyer devait donc être ramené à 9'540 fr. par an, charges et frais accessoires non compris, avec effet au 1er juillet 2005. La cause n'ayant pas été conciliée, les locataires ont ouvert action auprès du Tribunal des baux et loyers de Genève. Devant cette juridiction, la bailleresse a soulevé l'exception d'incompétence. Par jugement du 8 septembre 2008, le Tribunal des baux et loyers s'est déclaré incompétent pour examiner le litige portant sur l'adaptation du loyer survenue le 9 mars 2005, considérant que cette question relevait de la LCAP et avait été tranchée définitivement, faute de recours, par l'Office fédéral du logement dans sa décision du 10 janvier 2008. Statuant par arrêt du 20 avril 2009, la Chambre d'appel en matière de baux et loyers du canton de Genève a confirmé ce jugement. C. Les locataires exercent un recours en matière civile au Tribunal fédéral contre l'arrêt précité. Invoquant une violation des art. 18, 253b al. 3 et 274d al. 3 CO ainsi que 9 Cst., ils concluent à l'annulation de la décision attaquée, à la constatation de la compétence ratione materiae de la juridiction des baux et loyers et au renvoi de la cause à l'autorité cantonale; subsidiairement, ils demandent au Tribunal fédéral de constater lui-même que la hausse de loyer ne peut pas dépasser 6 % tous les deux ans et que le loyer doit donc être fixé à 9'540 fr. par année, charges non comprises, dès le 1er juillet 2005, avec restitution du trop-perçu. L'intimée propose le rejet du recours et la confirmation de l'arrêt déféré. 