Faits:
A. Par contrat du 25 avril 2006, la SI Y._ a remis à bail à H.X._ et F.X._, dès le 1er mai 2006, un appartement de quatre pièces d'une surface de 82 m2 situé au 8ème étage d'un immeuble, à Genève, ainsi qu'une place de parc extérieure. Selon avis officiel du 28 avril 2006, le loyer annuel de l'appartement, charges non comprises, s'élève à 17'640 fr. (1'470 fr. par mois) et se situe dans les limites des loyers usuels du quartier; le loyer annuel net payé par le locataire précédent était de 12'516 fr. (1'043 fr. par mois). L'acompte annuel pour les frais de chauffage a été fixé à 1'620 fr. (135 fr. par mois); un second acompte, du même montant, est perçu pour les frais d'exploitation. Les locataires se sont engagés à fournir une garantie bancaire de 4'410 fr.
Construit en 1955, l'immeuble qui abrite le logement loué est en bon état. Situé dans une zone de verdure du quartier de Saint-Jean, il est proche des commerces, écoles et transports publics. Lors de l'état des lieux d'entrée du 1er mai 2006, il a été constaté que la cuisine, agencée mais pas équipée, était ancienne et avait conservé ses faïences d'origine; la salle de bains et le WC séparé étaient récents; le sol était en parquet; seules les deux chambres étaient pourvues de fenêtres à double vitrage; la peinture des murs et des plafonds était «en ordre» mais nécessitait «diverses petites retouches». Les locataires se sont engagés à ne pas exiger, lors de la reprise de l'appartement, des travaux de rafraîchissement de la part de la bailleresse.
B. Le 23 mai 2006, H.X._ et F.X._ ont déposé une requête en contestation du loyer initial. Après l'échec de la conciliation, ils ont saisi le Tribunal des baux et loyers du canton de Genève. A titre préalable, ils demandaient la production par la bailleresse de toutes les pièces permettant d'effectuer un calcul de rendement. Principalement, leurs conclusions tendaient à la fixation du loyer annuel de l'appartement à 10'980 fr. (915 fr. par mois), charges non comprises, à la réduction de la garantie de loyer à due concurrence, à la libération du surplus de sûretés ainsi qu'à la condamnation de la bailleresse à rembourser le trop-perçu de loyer.
Par jugement du 21 juin 2007, le Tribunal des baux et loyers a débouté les locataires de leurs conclusions.
Statuant le 4 février 2008 sur appel des locataires, la Chambre d'appel en matière de baux et loyers du canton de Genève a annulé le jugement de première instance; elle a fixé le loyer mensuel à 1'300 fr., charges non comprises, et réduit les sûretés à 3'900 fr., la bailleresse étant condamnée à restituer le trop-perçu de loyer et à faire libérer la part de garantie dépassant le montant fixé. En substance, la cour cantonale a considéré le loyer convenu dans le bail comme abusif dès lors que la bailleresse n'avait pas donné suite à l'injonction du Tribunal des baux et loyers de fournir les documents nécessaires au calcul du rendement net de l'immeuble en cause. Se fondant sur deux statistiques cantonales et sur les caractéristiques du logement, la Chambre d'appel a arrêté ensuite le nouveau loyer mensuel à 1'300 fr., montant qui «se situe à mi-chemin entre le 3ème quartile du loyer des appartements de 4 pièces à loyer libre sis en Ville de Genève dans des immeubles construits entre 1951 et 1955 (1'320 fr.) et le loyer d'un appartement à loyer libre non neuf en Ville de Genève (1'287 fr.)».
C. H.X._ et F.X._ interjettent un recours en matière civile. Ils concluent à l'annulation de l'arrêt cantonal, puis à la fixation du loyer mensuel, sans les charges, à 1'165 fr. et à la réduction des sûretés à 3'495 fr., la bailleresse étant condamnée à rembourser, respectivement à faire libérer les montants perçus en trop.
La SI Y._ propose, principalement, le rejet du recours et, subsidiairement, le renvoi de la cause à l'autorité cantonale.

Considérant en droit:
1. 1.1 Interjeté par les demandeurs qui n'ont pas obtenu entièrement gain de cause (<ref-law>), le recours est dirigé contre un jugement final (<ref-law>) rendu en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>). Devant la Chambre d'appel, les recourants avaient conclu à ce que le loyer initial fût fixé à 10'890 fr. par an, sans les charges. La différence avec le loyer annuel convenu et confirmé dans le jugement de première instance est de 6'750 fr. (17'640 - 10'890) (<ref-law>). En multipliant ce montant par vingt (<ref-law>; cf. <ref-ruling> consid. 1 p. 424), on obtient une valeur litigieuse largement supérieure au seuil de 15'000 fr. fixé dans les affaires pécuniaires relevant du droit du bail à loyer (<ref-law>). Déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi, le recours est en principe recevable.
1.2 Le recours en matière civile peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. En vertu de l'exception ancrée à l'<ref-law>, le Tribunal fédéral n'entre pas en matière sur la violation d'un droit de rang constitutionnel ou sur une question afférente au droit cantonal ou intercantonal si le grief n'a pas été invoqué et motivé de manière détaillée par la partie recourante. Pour le reste, il applique le droit d'office (<ref-law>), sans être limité par les arguments soulevés dans le recours ni par la motivation retenue dans la décision attaquée; il peut donc admettre un recours pour d'autres motifs que ceux qui ont été articulés ou, à l'inverse, rejeter un recours en substituant une nouvelle argumentation à celle de l'autorité précédente. Cependant, compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sanctionnée par l'irrecevabilité des recours dont la motivation est manifestement insuffisante (<ref-law>), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est donc 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. 104).
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 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.3; <ref-ruling> consid. 1.4). 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 locataires ne remettent en cause ni le recours aux statistiques cantonales, ni les données chiffrées sur lesquelles la Chambre d'appel s'est fondée pour fixer le loyer initial. En revanche, ils reprochent à la cour cantonale de n'avoir pas tenu compte du fait que les seules charges non prises en compte dans les statistiques genevoises sont celles afférentes au chauffage et à la production d'eau chaude, alors que le bail liant les parties prévoyait deux sortes de frais accessoires facturés séparément, les frais de chauffage et les frais d'exploitation.
En fixant ainsi le loyer annuel admissible à 15'600 fr., sans les charges, sur la base des statistiques cantonales, la Chambre d'appel ferait payer deux fois les frais d'exploitation aux locataires, ce qui constituerait une violation des art. 257 et 257a CO.
Les juges genevois auraient également abusé de leur pouvoir d'appréciation, en violation des <ref-law> et 269 ss CO. Appliquant les règles du droit et de l'équité, l'autorité appelée à fixer le loyer initial devait apprécier d'une manière objective tous les éléments pertinents et rechercher la solution adéquate dans les circonstances du cas particulier. Or, selon les recourants, la cour cantonale a omis en l'occurrence de tenir compte d'un élément important, soit le fait que les loyers pris en compte dans les statistiques englobent les frais d'exploitation, contrairement au loyer convenu par les parties.
En conclusion, les recourants demandent que les frais d'exploitation mensuels par 135 fr. soient déduits du loyer net de 1'300 fr. par mois fixé par la cour cantonale.
2.2 Dans l'avis de fixation du loyer du 28 avril 2006, la bailleresse s'est référée au critère des loyers usuels du quartier (<ref-law>). En procédure, les locataires ont opposé le moyen tiré du rendement abusif (<ref-law>). La bailleresse n'a pas donné suite à l'ordonnance du Tribunal des baux et loyers l'invitant à fournir les pièces nécessaires au calcul de rendement. Dans son jugement, le tribunal s'est borné à examiner le loyer convenu sous l'angle du critère des loyers usuels du quartier; après avoir constaté que les éléments de comparaison produits par la bailleresse n'étaient pas suffisants, il a confirmé néanmoins le loyer figurant dans le bail sur la base d'une statistique cantonale.
Pour sa part, la Chambre d'appel a jugé que, même si l'immeuble avait été construit dans les années 1950, les locataires étaient en droit d'exiger un calcul de rendement en l'espèce. Aussi la bailleresse ne pouvait-elle pas se soustraire à l'injonction du tribunal de fournir les documents propres à effectuer un calcul de rendement, d'autant plus qu'elle n'avait jamais tenté de démontrer qu'un tel calcul était irréalisable faute des pièces nécessaires ou que les investissements consentis étaient sans rapport avec la réalité actuelle. La cour cantonale en a déduit que le loyer initial convenu dans le bail était abusif. Elle a posé ensuite qu'un loyer abusif était illicite et, partant, nul. Se référant aux arrêts publiés aux <ref-ruling> et 124 III 62, elle a fixé le loyer initial par appréciation, en se fondant sur toutes les circonstances du cas. Plus précisément, elle a choisi de s'appuyer sur plusieurs statistiques genevoises, malgré leurs défauts, en procédant aux réajustements nécessaires pour tenir compte des particularités du logement loué.
2.3 La jurisprudence à laquelle la cour cantonale se réfère s'applique lorsque la fixation du loyer initial est entachée d'un vice de forme. Dans ce cas-là, le bail est affecté d'une nullité partielle, limitée au loyer convenu. Il appartient alors au juge de fixer le loyer initial en se fondant sur toutes les circonstances du cas; parmi les facteurs à prendre en compte, il y a notamment le montant admissible selon l'<ref-law>, les loyers non abusifs pratiqués dans le quartier, le loyer payé par le précédent locataire. Jouissant d'un pouvoir plus étendu que dans la procédure en contestation d'un loyer fixé selon les formes prescrites, le juge n'a pas à restreindre son examen au caractère abusif ou non du loyer convenu, dont le montant constitue néanmoins la limite supérieure du loyer à fixer (<ref-ruling> consid. 5d et 6c; confirmé in <ref-ruling> consid. 2a et b).
En l'espèce, la situation est différente. Le contrat de bail liant les parties n'est pas entaché d'une nullité partielle liée à un vice de forme dans la fixation du loyer. Sur la base de l'appréciation des preuves, la cour cantonale a admis, ce qui n'est pas critiqué, que le loyer convenu de 1'470 fr. par mois était abusif. Il lui appartenait dès lors de réduire le montant du loyer dans la mesure admissible (cf. Roger Weber, Basler Kommentar, 4e éd., n. 8 et 8a ad <ref-law>; Peter Higi, Zürcher Kommentar, n. 57 ad <ref-law>). Contrairement à l'opinion de la Chambre d'appel, la jurisprudence précitée sur le pouvoir du juge appelé à fixer le loyer initial ne trouve pas à s'appliquer dans le cas présent; en particulier, le montant du loyer convenu, reconnu abusif, ne saurait constituer la limite supérieure du loyer à fixer.
Lorsque le loyer convenu a été considéré comme abusif en raison du refus du bailleur de produire les pièces qu'il détient (cf. <ref-law>), d'aucuns sont d'avis que le juge peut réduire le loyer initial convenu au montant faisant l'objet des conclusions - non-déraisonnables - du locataire (Sébastien Fetter, La contestation du loyer initial, thèse Berne 2005, n. 517, p. 237; Higi, op. cit., n. 86 ad <ref-law>; cf. également Weber, op. cit., n. 12a ad <ref-law>), voire au montant du loyer payé par le locataire précédent en cas d'augmentation importante (Fetter, ibid.).
En l'espèce, la cour cantonale a arrêté le loyer mensuel à 1'300 fr. en se référant à deux statistiques cantonales et aux particularités du logement loué. Les recourants ne s'en prennent pas à la méthode choisie dans l'arrêt attaqué, ni aux chiffres retenus en tant que tels. Ils concluent à la fixation du loyer mensuel à 1'165 fr., soit un montant plus élevé que celui figurant dans leurs conclusions devant la Chambre d'appel (907 fr.50) et que le loyer payé par le locataire précédent (1'043 fr.). Dans ces conditions, il n'est pas nécessaire de rechercher selon quels critères la cour cantonale aurait dû réduire le loyer convenu, ni de se prononcer sur le caractère suffisamment précis et différencié des statistiques genevoises (sur la question, <ref-ruling> consid. 4c; encore récemment, arrêt 4A_472/2007 du 11 mars 2008, consid. 2.2 et 2.4). Il sied uniquement d'examiner le moyen lié aux frais accessoires soulevé par les recourants.
2.4 La cour cantonale s'est fondée sur deux statistiques établies par l'Office cantonal de la statistique, figurant l'une dans l'«Annuaire statistique du canton de Genève» (2006) [statistique A] et l'autre dans «Etudes et documents - Le niveau des loyers à Genève» (n° 43, octobre 2006) [statistique B]. Le premier document indique que le montant par m2 correspond à un loyer sans charges (p. 150, note de pied 1). Dans la présentation du second document, il est précisé que le loyer pris en compte dans les statistiques «ne comprend pas les charges entraînées par le chauffage et l'eau chaude ou les provisions correspondantes» et que «si, dans le bail, le loyer destiné à la rente du capital est distingué des frais d'exploitation, le total des deux est pris en compte» (p. 4). Il s'ensuit que les frais accessoires autres que ceux liés au chauffage et à la production d'eau chaude sont englobés dans les loyers servant de données pour les statistiques cantonales. Or, dans le bail liant les parties, les frais d'exploitation, distingués des frais de chauffage, font l'objet d'un acompte séparé et ne sont donc pas inclus dans le loyer net. En ne prenant pas en considération la facturation séparée de ces frais accessoires-là, la cour cantonale a omis un élément pertinent dans la fixation du loyer initial sur la base de statistiques. Comme les recourants le relèvent à juste titre, cette omission conduit à faire payer aux locataires deux fois les frais d'exploitation. Il y a là une violation du droit fédéral, singulièrement des art. 257, 257a al. 2 et 257b al. 1 CO.
2.5 Les recourants proposent de déduire du loyer mensuel de 1'300 fr. retenu par la cour cantonale le montant de 135 fr. par mois versé à titre d'acompte pour les frais d'exploitation. Certes, ce montant ne correspond pas nécessairement au franc près aux frais d'exploitation qui seront effectivement facturés dans le décompte annuel. On peut toutefois partir de l'idée que l'acompte exigé par la bailleresse représente une bonne indication du montant de ces frais accessoires, d'autant plus que, si l'on se réfère à l'avis de fixation de loyer du 28 avril 2006, l'acompte mensuel venait de passer de 131 fr. pour les locataires précédents à 135 fr. dans le nouveau bail. En conséquence, il convient de fixer le loyer initial net à 1'165 fr. par mois, ce qui, malgré la facturation séparée des frais d'exploitation, est encore supérieur au loyer mensuel moyen selon l'époque de construction (13 fr.80 x 82 = 1'131 fr.60), respectivement selon le quartier (13 fr.30 x 82 = 1'090 fr.60) [statistique A]. Il est également à noter que si l'on ajoutait le montant de 135 fr. au loyer mensuel de 1'300 fr. fixé par la cour cantonale, le loyer mensuel net serait de 1'435 fr., montant qui s'approche des loyers les plus élevés pour un appartement de quatre pièces en ville dans un immeuble construit entre 1951 et 1955 [statistique B] ainsi que des loyers moyens pour un logement de quatre pièces dans les quartiers de Champel ou de Florissant, notoirement plus chers que le quartier de Saint-Jean [statistique A].
2.6 En conclusion, le recours sera admis et l'arrêt attaqué sera réformé en ce sens que le loyer initial, sans les frais de chauffage et d'exploitation, est fixé à 1'165 fr. par mois; en conséquence, la bailleresse remboursera aux locataires la part de loyers perçue en trop depuis le début du contrat et fera libérer en leur faveur la part des sûretés fournies dépassant le montant du nouveau loyer multiplié par trois (cf. <ref-law>).
Dès lors que la cour cantonale a condamné l'intimée à payer l'émolument d'appel, il ne se justifie pas de répartir autrement les frais de la procédure cantonale (cf. <ref-law>). Faute de décision de l'autorité précédente sur les dépens, il n'y a pas lieu non plus d'appliquer l'<ref-law>.
3. Vu l'admission du recours, les frais judiciaires seront pris en charge par l'intimée (<ref-law>), laquelle versera en outre des dépens aux recourants (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'arrêt attaqué est réformé dans le sens suivant:
Le loyer dû dès le 1er mai 2006 par H.X._ et F.X._ à la SI Y._ pour la location de l'appartement de quatre pièces situé au 8ème étage de l'immeuble sis ..., à Genève, est fixé à 1'165 fr. par mois, frais de chauffage et d'exploitation non compris.
La SI Y._ est condamnée à rembourser à H.X._ et F.X._ la somme de 305 fr. par mois pour la période courant du 1er mai 2006 jusqu'à la réduction effective du loyer.
Le montant des sûretés constituées par les locataires est réduit à 3'495 fr.
La SI Y._ est condamnée à faire libérer en faveur de H.X._ et de F.X._ la différence avec les sûretés constituées, soit 915 fr.
L'arrêt attaqué est confirmé pour le surplus.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge de l'intimée.
3. L'intimée versera aux recourants, créanciers solidaires, une indemnité de 3'500 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux mandataires des parties et à la Chambre d'appel en matière de baux et loyers du canton de Genève.
Lausanne, le 10 juin 2008
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
Le Président: La Greffière:
Corboz Godat Zimmermann