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. 