Faits: A. Selon contrat conclu le 17 mars 2006 avec Z._ SA, les époux F.X._ et H.X._ ont pris à bail un appartement de cinq pièces avec hall, cuisine agencée, salle de bain, WC séparé et salle de douche au troisième étage d'un bâtiment sis à Pully. Le loyer mensuel net était fixé à 1'900 francs. Les frais de chauffage, d'eau chaude et les frais accessoires étaient dus en sus; ces derniers comprendraient « les charges de préférence et les taxes publiques, telles que taxe d'épuration des eaux (entretien et utilisation), taxe d'égout et taxe d'enlèvement des ordures »; les locataires verseraient un acompte mensuel de 220 francs. Le 14 du même mois, usant d'une formule officielle, la bailleresse avait communiqué que le locataire précédent avait acquitté un loyer mensuel au montant de 1'323 fr., plus 220 fr. d'acompte pour chauffage et eau chaude. L'augmentation du loyer était motivée par « l'adaptation aux loyers usuels du quartier ou de la localité ». La bailleresse répéta cette communication le 27 mars, dans les mêmes termes, mais en ajoutant « en outre, nous signalons que cet appartement a fait l'objet d'une rénovation complète pour un montant de 51'000 fr. ». B. Le 25 avril 2006, devant la commission de conciliation compétente puis devant le Tribunal des baux du canton de Vaud, les époux X._ ont ouvert action contre Z._ SA. Leur demande tendait à faire réduire le loyer de l'appartement, dès le 15 avril 2006, au montant de 900 fr. par mois. La défenderesse devait être condamnée à rembourser aux demandeurs les sommes payées par eux, à titre de loyer, au delà de ce même montant, avec intérêts au taux de 5% par an dès le 25 avril 2006. A la banque concernée, le tribunal devait ordonner la libération immédiate de 3'000 fr. sur la garantie que les demandeurs avaient constituée en faveur de l'autre partie. La défenderesse a conclu au rejet de l'action. Le tribunal s'est prononcé le 4 juin 2007. Accueillant partiellement l'action, il a jugé que la défenderesse avait échoué dans la preuve des loyers usuels dans le quartier ou la localité, de sorte que le loyer convenu entre les parties se révélait abusif. Le taux hypothécaire avait considérablement diminué depuis la plus récente fixation du loyer du locataire précédent, de sorte que ce loyer-ci, quoique très inférieur, était lui aussi abusif. Sur la base de ce même loyer, en tenant dûment compte de l'évolution respective du taux hypothécaire et de l'indice suisse des prix à la consommation, et aussi des plus-values que la défenderesse avait apportées à l'appartement en y exécutant des travaux de rénovation, le loyer mensuel devait être fixé à 1'132 fr., avec références à 3% pour le taux hypothécaire et à 155,1 points pour l'indice des prix à la consommation, base 1983 (recte: décembre 1982). La défenderesse était condamnée à rembourser 5'760 fr. avec intérêts au taux de 5% par an dès le 5 décembre 2006; la banque devait libérer 2'304 fr. sur la garantie constituée par les demandeurs. Le tribunal a rejeté des conclusions additionnelles tendant à faire prononcer que les frais accessoires, autres que ceux de chauffage et d'eau chaude, n'incombaient pas aux demandeurs, au motif que ce chef de la contestation n'avait pas été soumis à la commission de conciliation. C. La défenderesse ayant recouru contre le jugement, les demandeurs ont usé du recours incident. Selon leurs conclusions, le loyer devait être fixé à 1'015 fr.35 par mois avec les mêmes références au taux hypothécaire et à l'indice des prix; la défenderesse devait rembourser, avec intérêts dès le 5 décembre 2006, 6'634 fr.90, et la garantie devait être réduite de 2'653 fr.95. La Chambre des recours du Tribunal cantonal a statué le 1er octobre 2008. Elle a jugé que, contrairement à l'opinion des premiers juges, la défenderesse avait fourni en nombre suffisant des exemples pertinents et concluants, aptes à mettre en évidence les loyers usuels dans le quartier ou la localité, de sorte que le loyer convenu entre les parties n'était pas abusif. En conséquence, réformant le jugement, la chambre a rejeté l'action. D. Agissant par la voie du recours en matière civile, les demandeurs saisissent le Tribunal fédéral de conclusions semblables à celles déjà prises devant la Chambre des recours. La défenderesse conclut au rejet du recours, dans la mesure où celui-ci est recevable. 