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 <ref-law> 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é.

Considérant en droit:
1. 1.1 La cour cantonale a estimé que le présent litige relatif à l'adaptation du loyer s'inscrivait directement dans le rapport de droit public liant la bailleresse à la Confédération, car le loyer initial avait pu être baissé grâce à l'aide de l'Etat fédéral. Les recourants font valoir que la hausse de loyer contestée doit être examinée à la lumière des normes de droit privé régissant le bail à loyer (<ref-law>). Selon la jurisprudence, une contestation de cette nature ressortit au droit privé (ATF128 III 250 consid. 1a et les arrêts cités).
1.2 La décision attaquée, qui confirme le jugement de première instance, est une décision d'incompétence. Dès lors qu'elle met fin à la procédure civile engagée, il s'agit d'une décision finale au sens de l'<ref-law> (BERNARD CORBOZ, in Commentaire de la LTF, Berne 2009, n° 13 ad <ref-law>).
Le litige porte sur une différence de loyer de 804 fr. par an (10'344 fr. - 9'540 fr.). Comme cette divergence va se perpétuer d'année en année et que le contrat est conclu pour une durée indéterminée, il faut multiplier ce montant par vingt pour déterminer la valeur litigieuse (<ref-law>; <ref-ruling> consid. 1 p. 399), de sorte que le seuil minimal de 15'000 fr. prescrit en matière de baux et loyers (<ref-law>) est atteint.
Interjeté par les parties qui ont en pratique succombé dans leur opposition à la hausse de loyer (<ref-law>) et dirigé contre un arrêt rendu en dernière instance cantonale (<ref-law>), le recours est en principe recevable, puisqu'il a été déposé dans le délai (art. 48 al. 1 et 100 al. 1 LTF) et la forme (<ref-law>) prévus par la loi.
1.3 Le recours en matière civile peut être interjeté pour violation du droit fédéral (<ref-law>), y compris le droit constitutionnel (<ref-ruling> consid. 1.2 p. 382). Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est pas limité par les arguments soulevés dans le recours ni par la motivation retenue par l'autorité précédente; il peut donc admettre un recours pour d'autres motifs que ceux qui ont été articulés, ou à l'inverse, rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.1 et l'arrêt cité). Il s'en tient cependant d'ordinaire aux questions juridiques que la partie recourante soulève dans la motivation du recours (<ref-law>; <ref-ruling> consid. 1.1 p. 105). Il n'examine la violation de droits constitutionnels que s'il est saisi d'un grief invoqué et motivé de façon détaillée (<ref-law>; <ref-ruling> consid. 3.2 p. 88; <ref-ruling> consid. 1.4.2 p. 254).
1.4 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 constatations factuelles de l'autorité cantonale ont été établies de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.5 p. 130; <ref-ruling> consid. 4.3) - 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. Le recourant ne peut de toute manière 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>).
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 Dans l'arrêt attaqué, la cour cantonale a considéré que le litige opposant les parties relevait de la juridiction administrative, et non pas du juge civil; elle s'est donc déclarée incompétente pour en connaître.
Les recourants soutiennent au contraire que la bailleresse s'est engagée à leur égard, sur une base purement contractuelle, à ne pas appliquer des hausses de loyer dépassant 6 % tous les deux ans, de sorte que le litige porte sur le respect d'un engagement de droit privé et que la juridiction des baux et loyers devait en connaître. Ils font grief à la Chambre d'appel d'avoir mal appliqué l'<ref-law>.
2.2 Selon la norme précitée, les dispositions relatives à la contestation des loyers abusifs ne s'appliquent pas aux locaux d'habitation en faveur desquels des mesures d'encouragement ont été prises par les pouvoirs publics et dont le loyer est soumis au contrôle d'une autorité.
Cette disposition remplit plusieurs fonctions.
Tout d'abord, elle délimite le champ d'application des dispositions du code des obligations relatives au bail à loyer (titre huitième du CO). Elle prévoit ainsi que le chapitre 2 (<ref-law>) n'est pas applicable aux logements subventionnés dont le loyer est soumis à un contrôle de l'autorité. L'<ref-law> le confirme a contrario, en énumérant les dispositions qui sont applicables à cette catégorie de logements. Il en résulte que tous les mécanismes permettant au juge civil de se prononcer sur le loyer admissible sont clairement écartés, à savoir la contestation du loyer initial (<ref-law>), la contestation d'une augmentation de loyer (<ref-law>), la demande de réduction de loyer (<ref-law>) et la contestation du loyer indexé (<ref-law>).
L'<ref-law> trace aussi une frontière entre le droit privé et le droit public. Dans le cadre de sa politique sociale du logement, la collectivité publique peut accorder une aide financière à des propriétaires dans le but d'abaisser le montant des loyers et de répondre ainsi au besoin d'une partie de la population. De telles mesures relèvent à l'évidence du droit public. Pour qu'elles puissent atteindre leur but, il est nécessaire que la collectivité publique ait la faculté d'exercer un contrôle sur la fixation des loyers. La situation présente donc une certaine complexité, puisqu'il existe, d'une part, un rapport de droit public entre la collectivité et le propriétaire qui impose à ce dernier certaines charges et, d'autre part, un contrat de bail entre le propriétaire et le locataire, lequel relève en principe du droit privé. Face à cette difficulté, le législateur n'a pas prévu un système dualiste à l'<ref-law>, mais il a au contraire voulu que les mécanismes du droit privé s'effacent devant le contrôle d'office par l'autorité administrative, jugé plus incisif.
L'<ref-law> doit aussi être considéré comme une norme fédérale de compétence (<ref-ruling> consid. 4b/dd p. 467; cf. aussi arrêt 4C.73/2004 du 1er juin 2004 consid 1.1, in SJ 2005 I p. 20). La ratio legis de l'<ref-law> est évidemment d'empêcher un double contrôle des loyers et d'éviter le prononcé de décisions contradictoires; pour les habitations qui font l'objet de mesures d'encouragement par les pouvoirs publics, l'autorité chargée du contrôle des loyers jouit d'une compétence exclusive, et la procédure prévue dans le droit des obligations est fermée (<ref-ruling> consid. 4b/dd p. 466; cf. aussi: <ref-ruling> consid. 2.6.2).
2.3 En l'espèce, les recourants reconnaissent que l'immeuble dans lequel ils occupent des locaux d'habitation bénéficie de mesures d'encouragement de la part des pouvoirs publics et que le montant des loyers est soumis au contrôle d'une autorité administrative. Il n'est donc pas contesté que les conditions d'application de l'<ref-law> sont remplies.
En vertu de cette norme fédérale de compétence, les moyens de droit prévus par le code des obligations pour permettre au locataire de contester le montant du loyer ne sont pas ouverts aux recourants.
Il faut d'ailleurs observer que, pour répondre à certaines critiques, l'<ref-law> a été introduit, afin de permettre au locataire, quand bien même il n'est pas partie au rapport de droit public, de contester le loyer fixé en lui ouvrant la voie de la juridiction administrative (<ref-ruling> consid. 2.6 p. 131 s.).
Du moment que la fixation du loyer d'espèce, qui relève de la LCAP, est de la compétence exclusive de l'autorité administrative fédérale, c'est à juste titre que la juridiction cantonale a décliné sa compétence. On ne discerne à cet égard aucune violation de l'<ref-law>.
2.4 Comme la question de la compétence est régie par le droit fédéral, le droit cantonal n'était pas applicable. Partant, l'argumentation des recourants concernant une violation arbitraire (art. 9 Cst.) de la règle cantonale de compétence est dépourvue d'objet.
2.5 Les recourants tentent de soutenir, en se référant à l'<ref-law>, qu'ils sont au bénéfice d'un engagement purement privé qui leur permettrait de s'opposer à une hausse de loyer dépassant 6 %. Mais admettre que des accords entre bailleur et locataire puissent se superposer au système de la LCAP et permettre à deux autorités différentes de statuer de manière contradictoire sur le même loyer irait à l'encontre du but poursuivi par le législateur à l'<ref-law> (cf. arrêt 4C.12/1998 du 27 octobre 1998 consid. 4b). Il apparaît donc que les locataires devaient faire valoir leurs arguments devant l'autorité administrative, seule compétente en la matière.
L'affaire ayant été correctement instruite et les recourants ayant pu faire valoir leurs moyens, on ne discerne aucune violation de l'<ref-law>.
Les locataires prétendent certes qu'ils ont été induits en erreur par leur partie adverse. Il n'y a toutefois pas lieu d'examiner le cas sous l'angle de l'erreur essentielle (<ref-law>) ou du dol (<ref-law>) puisqu'ils n'ont pas invalidé le contrat dans l'année (<ref-law>).
Le recours doit donc être rejeté.
3. Les frais judiciaires et les dépens sont mis solidairement à la charge des recourants qui succombent (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 1'000 fr., sont mis solidairement à la charge des recourants.
3. Les recourants sont condamnés solidairement à verser à l'intimée une indemnité de 2'000 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Chambre d'appel en matière de baux et loyers du canton de Genève.
Lausanne, le 7 août 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Le Greffier:
Klett Ramelet