Faits:
A. Par contrat du 11 février 2004, la Z._ (ci-après : la bailleresse) a cédé à X._ et Y._ (ci-après : les locataires) l'usage d'un appartement de cinq pièces au Grand-Lancy (GE), moyennant le paiement d'un loyer mensuel de 1'720 fr., auquel s'ajoutent 120 fr. à titre de provision pour les charges. Le contrat a été conclu pour une durée initiale de cinq ans, commençant le 1er mars 2004 et se terminant le 28 février 2009. Il contient une clause de tacite reconduction, indiquant qu'il se renouvelle ensuite, sauf résiliation donnée par l'une des parties, de cinq ans en cinq ans. Il a été convenu que le loyer pouvait être adapté en cours de bail en fonction de l'évolution de l'indice officiel suisse des prix à la consommation, moyennant un préavis écrit d'un mois au moins et à raison d'une fois tous les douze mois au maximum. Il est précisé que l'indice de référence est celui du 31 janvier 2004.
Par avis du 17 septembre 2007, la bailleresse a notifié une hausse de loyer prenant effet au 1er novembre 2007 et portant le loyer à 1'783 fr. sans les charges. Cette hausse est fondée sur l'évolution de l'indice entre le 31 janvier 2004 et le 31 août 2007.
Le contrat n'ayant pas été résilié pour son échéance, il s'est renouvelé, conformément à la clause de tacite reconduction, pour la période du 1er mars 2009 au 28 février 2014.
Le 16 septembre 2009, la bailleresse a notifié un second avis de hausse, avec effet dès le 1er novembre 2009, portant le loyer mensuel à 1'820 fr., charges non comprises. Il était invoqué la variation de l'indice entre le 31 août 2007 (indice de référence de la précédente hausse) et le 31 août 2009.
Les locataires se sont opposés à cette hausse de loyer.
B. A la suite de l'échec de la tentative de conciliation, le Tribunal des baux et loyers du canton de Genève, saisi par la bailleresse, a fixé, par jugement du 15 septembre 2010, à 1'790 fr., charges non comprises, le loyer mensuel dû dès le 1er novembre 2009. Les premiers juges ont considéré que la bailleresse, en ne notifiant pas de hausse lors de la reconduction du bail, avait montré que le loyer fixé à cette date lui convenait et que l'indexation devait en conséquence être calculée à partir de la date de la reconduction. L'augmentation a donc été calculée sur la base de l'indice de février 2009.
Saisie d'un appel formé par la bailleresse, la Chambre d'appel en matière de baux et loyers du canton de Genève, par arrêt du 11 avril 2011, a annulé le jugement attaqué et validé la hausse notifiée par la bailleresse, fixant le loyer à 21'840 fr. par an, charges non comprises, dès le 1er novembre 2009. La cour cantonale a considéré que, par la tacite reconduction, les parties étaient restées liées, de manière continue, par la même clause d'indexation, de sorte que la hausse devait être déterminée en fonction de l'évolution de l'indice à compter de la précédente fixation du loyer.
C. Les locataires exercent un recours en matière civile au Tribunal fédéral, ainsi qu'un recours constitutionnel subsidiaire, contre l'arrêt cantonal du 11 avril 2011. Admettant que la valeur litigieuse requise pour un recours en matière civile n'était pas atteinte, ils soutiennent que le litige pose une question de principe, non réglée clairement, qui est susceptible de se reproduire constamment. Ils soutiennent l'opinion des juges de première instance et concluent, avec suite de frais et dépens, à l'annulation de l'arrêt attaqué et à la fixation du loyer annuel à 21'480 fr., sans les charges, dès le 1er novembre 2009.
L'intimée a conclu au rejet du recours avec suite de frais et dépens.

Considérant en droit:
1. 1.1 Le recours en matière civile n'est en principe ouvert, dans le domaine du droit du bail, que si la valeur litigieuse atteint au moins 15'000 fr. (<ref-law>).
En l'espèce, la bailleresse a conclu, devant l'autorité précédente, à ce que le loyer soit fixé à 21'840 fr. par an, tandis que les locataires ont conclu à un loyer de 21'480 fr. La différence entre ces deux conclusions - qui constituait l'objet du litige - n'est donc que de 360 fr. par an (21'840 fr. - 21'480 fr.). Si l'on multiplie ce chiffre par vingt (<ref-law>; <ref-ruling> consid. 1 p. 399; <ref-ruling> consid. 1 p. 424), on obtient un total de 7'200 fr., de sorte que la valeur litigieuse est insuffisante. Ce point n'est pas litigieux.
Le recours en matière civile est néanmoins recevable si la contestation soulève une question juridique de principe (<ref-law>). Les recourants se prévalent de cette disposition et, conformément aux exigences de l'art. 42 al. 2 deuxième phrase LTF, ils ont expliqué de manière précise en quoi la contestation soulève une question juridique de principe (cf. arrêt 4A_546/2010 du 17 mars 2011 consid. 1.1 non publié in <ref-ruling>).
La jurisprudence a souligné qu'il fallait se montrer restrictif dans l'admission d'une dérogation à l'exigence de la valeur litigieuse sur la base de l'<ref-law>. Elle s'est efforcée de cerner la notion de contestation soulevant une question juridique de principe (<ref-ruling> consid. 1.3 p. 4 s., 397 consid. 1.2 p. 399; <ref-ruling> consid. 1.2 p. 269, 354 consid. 1.3 p. 357). En résumé, il faut qu'il soit nécessaire, pour résoudre le cas d'espèce, de trancher une question juridique qui donne lieu à une incertitude caractérisée, laquelle appelle de manière pressante un éclaircissement de la part du Tribunal fédéral, en tant qu'autorité judiciaire suprême chargée de dégager une interprétation uniforme du droit fédéral (<ref-ruling> consid. 1.2 p. 399).
Le Tribunal fédéral n'a jamais tranché la question, telle qu'elle est maintenant posée. Dans l'<ref-ruling>, il s'est concentré sur l'hypothèse d'une clause d'indexation qui arrive à expiration; examinant la validité d'une majoration de loyer notifiée pour l'échéance contractuelle, il a admis que les deux parties pouvaient demander un calcul selon la méthode absolue. Il a précisé que si les parties optent pour la méthode relative, il faut garder à l'esprit que les facteurs ordinaires de variation du loyer ne peuvent pas être pris en compte pendant la durée de validité de la clause d'indexation. En conséquence, il est possible de remonter au-delà de la dernière fixation du loyer jusqu'au début de la période de validité de la clause d'indexation, mais pas au-delà de la dernière reconduction tacite (<ref-ruling> consid. 4 p. 27 ss). Cette jurisprudence a été confirmée plusieurs fois par la suite (<ref-ruling> consid. 1b/bb p. 362; arrêt 4A_489/2010 du 6 janvier 2011 consid. 4.2; arrêt 4C.157/2001 du 1er octobre 2001 consid. 1a et b). Elle ne traite cependant pas la question posée en l'espèce, qui porte exclusivement sur l'application d'une clause d'indexation qui a été valablement reconduite tacitement pour une nouvelle période de cinq ans (cf. art. 269b, 270c CO; art. 17 et 18 OBLF; <ref-ruling> consid. 3b p. 60; <ref-ruling> consid. 4a p. 77).
L'autorité précédente explique elle-même que la jurisprudence cantonale a varié sur cette question, de sorte qu'il faut admettre l'existence d'une incertitude caractérisée.
Les parties n'ayant pu citer aucun auteur qui s'exprime sur la question, on ne saurait parler d'une doctrine bien établie.
La question pourrait à nouveau se poser en tout temps et peut-être sans qu'une valeur litigieuse suffisante ne soit jamais atteinte. Il faut donc admettre que la contestation soulève une question juridique de principe, de sorte que le recours en matière civile est ouvert, ce que l'intimée ne conteste d'ailleurs pas. Il en résulte que le recours constitutionnel, qui a été interjeté par précaution, est irrecevable, puisqu'il revêt un caractère subsidiaire (<ref-law>).
1.2 Interjeté par les parties qui ont succombé dans leurs conclusions sur le montant du loyer de leur habitation et qui ont donc qualité pour recourir (<ref-law>), dirigé contre un arrêt final (<ref-law>) rendu en matière civile (<ref-law>) par une autorité cantonale de dernière instance statuant sur recours (<ref-law>), le recours en matière civile est en principe recevable, puisqu'il a été déposé dans le délai (art. 46 al. 1 let. a, 48 al. 1 et 100 al. 1 LTF) et la forme (<ref-law>) prévus par la loi.
1.3 Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF.
En l'espèce, les recourants soulèvent exclusivement une question de droit matériel fédéral. Le grief est donc recevable (<ref-law>) et le Tribunal fédéral peut même appliquer ce droit d'office (<ref-law>). Toutefois, compte tenu de l'exigence de motivation contenu à 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. 2.2.1 p. 389; <ref-ruling> consid. 1.4).
1.4 Le Tribunal fédéral conduit en principe son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). En l'espèce, les faits ne sont pas contestés et l'on ne voit aucun motif prévu par la loi pour y revenir d'office (<ref-law>). Il faut donc s'en tenir aux constatations cantonales.
1.5 Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (<ref-law>). Toute conclusion nouvelle est irrecevable (<ref-law>).
2. Lorsque des cocontractants conviennent d'une clause de tacite reconduction, ils acceptent qu'une absence de résiliation de leur part soit interprétée comme une volonté de poursuivre la relation contractuelle. La tacite reconduction signifie donc que les parties, en ne résiliant pas, sont convenues de maintenir leur contrat. Il est symptomatique d'observer que lorsqu'une hausse de loyer est notifiée pour l'échéance alors que le contrat se renouvelle tacitement, la jurisprudence parle volontiers d'une augmentation de loyer "en cours de bail" (cf. par exemple : <ref-ruling> consid. 4c p. 81). La reconduction tacite marque donc davantage la continuité dans la relation contractuelle plutôt qu'une césure.
Si l'on devait suivre l'opinion des recourants, il en résulterait qu'aucune des parties ne pourrait invoquer la variation de l'indice intervenue entre la dernière fixation du loyer et la fin de la précédente période de cinq ans. Il y aurait donc une brèche dans l'indexation. Or, on doit garder à l'esprit que les parties, expressément au moment de la conclusion du contrat puis tacitement au moment de la reconduction, ont exprimé la volonté de soumettre le loyer à la clause d'indexation, sans que l'on puisse discerner dans leur intention la moindre rupture pour toute la période allant du 1er mars 2004 au 28 février 2014.
Il faut relever que la bailleresse n'était tenue, ni en vertu d'une disposition légale, ni sur la base d'une clause contractuelle, de procéder à une indexation à l'expiration de la première période de cinq ans. On observe que la bailleresse n'a augmenté le loyer qu'une seule fois pendant la première période de cinq ans et on en déduit qu'elle ne voulait le faire que lorsque l'augmentation de l'indice était suffisamment significative. Cette manière de procéder est raisonnable et on ne voit pas pourquoi on devrait l'entraver en exigeant une indexation à la fin de chaque période de cinq ans alors que les parties conviennent tacitement de maintenir la clause d'indexation. Sous l'angle de la bonne foi, les locataires devaient déduire de l'attitude de la bailleresse qu'elle renonçait à notifier une augmentation de loyer aussi longtemps que la variation de l'indice n'était pas suffisamment importante. Ils ne pouvaient en revanche pas sérieusement s'imaginer que la bailleresse leur faisait cadeau de l'indexation entre la dernière fixation de loyer et la fin de la première période de cinq ans.
Lorsque les baux ne contiennent ni clause d'indexation, ni clause d'échelonnement, le loyer ne peut être modifié que pour l'échéance, c'est-à-dire le moment où s'opère, sauf résiliation, la tacite reconduction. On applique alors d'ordinaire la méthode relative et on recherche l'évolution des paramètres par rapport aux circonstances qui étaient connues au moment de la dernière fixation du loyer (ATF <ref-ruling> consid. 3 p. 425 ss). De jurisprudence constante, le moment déterminant pour la comparaison des situations est celui de la dernière fixation du loyer (<ref-ruling> consid. 2a p. 126; <ref-ruling> consid. 3 p. 69; <ref-ruling> consid. 2c p. 164), peu importe si, dans l'intervalle, il y a eu une reconduction tacite ne comportant aucune modification du loyer. La jurisprudence a même expressément retenu qu'une modification du bail qui ne remet pas en cause le montant du loyer, autrement dit qui ne constitue pas une nouvelle fixation du loyer en fonction de bases de calcul modifiées, ne saurait constituer un point de référence pour juger de l'admissibilité d'une adaptation postérieure (<ref-ruling> consid. 2a p. 126; arrêt 4A_489/2010 déjà cité consid. 4.1). Il n'y a pas de raison de trancher différemment la question qui est maintenant posée. Lors de la reconduction tacite, le contrat n'a été modifié que sur un point, à savoir l'échéance qui a été reportée du 28 février 2009 au 28 février 2014. Qu'il n'y ait pas d'autre changement est manifestement le sens de la clause contractuelle prévoyant qu'en l'absence de résiliation, le bail se poursuit aux conditions en vigueur à l'échéance. Le montant du loyer n'a pas été modifié, ni d'ailleurs la clause d'indexation qui en régit la fixation. Il n'y a dès lors pas eu une nouvelle fixation du loyer, qui puisse servir de référence pour le calcul de l'indexation.
En conclusion, lorsqu'un bail assorti valablement d'une clause d'indexation se renouvelle tacitement pour une durée de cinq ans au minimum, la prochaine indexation doit être calculée en se référant à l'indice connu au moment de la dernière fixation du loyer, sans égard à la reconduction tacite survenue dans l'intervalle.
Ainsi, la cour cantonale n'a pas violé le droit fédéral et le recours en matière civile doit être rejeté.
3. Les frais judiciaires et les dépens sont mis solidairement à la charge des recourants qui succombent (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 constitutionnel subsidiaire est irrecevable.
2. Le recours en matière civile est rejeté.
3. Les frais judiciaires, fixés à 1'000 fr., sont mis solidairement à la charge des recourants.
4. Les recourants verseront solidairement à l'intimée une indemnité de 2'000 fr. à titre de dépens.
5. Le présent arrêt est communiqué aux représentants des parties et à la Chambre d'appel en matière de baux et loyers du canton de Genève.
Lausanne, le 3 novembre 2011
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Piaget