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.

Considérant en droit:
1. Le recours est dirigé contre un jugement final (<ref-law>), rendu en matière civile (<ref-law>) et en dernière instance cantonale (<ref-law>). Ses auteurs ont pris part à l'instance précédente et succombé dans leurs conclusions (<ref-law>). La valeur litigieuse correspond à vingt fois la part du loyer annuel encore contestée dans cette même instance (art. 51 al. 1 let. a, 51 al. 4 LTF; <ref-ruling> consid. 1 p. 399; <ref-ruling> consid. 1 p. 424); elle excède le minimum légal de 15'000 fr. prévu en matière de droit du bail à loyer (<ref-law>). Introduit en temps utile (<ref-law>) et dans les formes requises (art. 42 al. 1 à 3 LTF), le recours est en principe recevable.
Le recours est ouvert pour violation du droit fédéral (<ref-law>). Le Tribunal fédéral applique ce droit d'office, hormis les droits fondamentaux (<ref-law>). Il n'est pas lié par l'argumentation des parties et il apprécie librement la portée juridique des faits; 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.4.1 p. 254), et il ne se prononce sur la violation de droits fondamentaux que s'il se trouve 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. 2.2 p. 246; <ref-ruling> consid. 1.4.2).
Le Tribunal fédéral doit conduire son raisonnement juridique sur la base des faits constatés dans la décision attaquée (<ref-law>); en règle générale, les allégations de fait et les moyens de preuve nouveaux sont irrecevables (<ref-law>). Le tribunal peut compléter ou rectifier même d'office les constatations de fait qui se révèlent manifestement inexactes, c'est-à-dire arbitraires aux termes de l'art. 9 Cst. (<ref-ruling> consid. 1.1.2 p. 252), ou établies en violation du droit (<ref-law>). La partie recourante est autorisée à attaquer des constatations de fait ainsi irrégulières si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>).
2. Selon l'<ref-law>, le loyer n'est « en règle générale » pas abusif s'il se situe dans les limites des loyers usuels dans la localité ou dans le quartier. Les demandeurs se plaignent d'une application incorrecte de cette disposition.
2.1 L'art. 11 al. 1 et 3 de l'ordonnance du Conseil fédéral sur le bail à loyer et le bail à ferme d'habitations et de locaux commerciaux (OBLF) prescrit que les loyers déterminants pour la constatation des loyers usuels, dans la localité ou le quartier, sont ceux des logements comparables à la chose louée, quant à leur emplacement, dimension, équipement, état et année de construction (al. 1), à l'exclusion, toutefois, des loyers résultant de ce qu'un bailleur ou un groupe de bailleurs domine le marché (al. 3).
En règle générale, le juge doit disposer d'au moins cinq éléments de comparaison. Il doit effectuer des comparaisons concrètes et l'autorité cantonale de dernière instance doit indiquer exactement les critères utilisés par elle; sur cette base, le Tribunal fédéral contrôle librement si les loyers usuels sont établis conformément au droit fédéral (<ref-ruling> consid. 4a p. 319; arrêt 4C.265/2000 du 16 janvier 2001, consid. 4, SJ 2001 I p. 247). Les loyers de référence doivent eux-mêmes n'être pas abusifs; il est donc nécessaire, en principe, de les adapter aux baisses du taux hypothécaire survenues depuis le moment où ils ont été fixés (<ref-ruling>).
2.2 La défenderesse a allégué sept exemples de logements loués qu'elle tenait pour aptes à la comparaison. Le Tribunal des baux en a d'emblée rejeté deux, au motif que l'identité du bailleur était inconnue et que l'on ne pouvait donc pas discerner s'il s'agissait réellement d'objets de comparaison distincts. Quatre autres exemples furent rejetés au motif que ces logements étaient tous administrés, comme celui des demandeurs, par la même gérance; de surcroît, deux de ces appartements ne se prêtaient pas à la comparaison en raison de leur équipement. En définitive, un seul des exemples pouvait être retenu, ce qui ne suffisait pas à établir les loyers usuels.
Après complément d'instruction, la Chambre des recours a constaté que les sept logements de comparaison appartiennent à des bailleurs différents. Selon son jugement, il est sans importance que quatre d'entre eux soient administrés par la même gérance. Un des logements de comparaison doit être écarté en raison de son état d'entretien; les caractéristiques des six autres « sont grosso modo comparables à celles de l'appartement litigieux, l'impression d'ensemble étant décisive ». Après adaptation de ces six loyers aux baisses du taux hypothécaire, leur moyenne s'élève à 1'911 fr.10, d'où la Chambre des recours conclut que le loyer litigieux, au montant de 1'900 fr., n'est pas abusif.
2.3 Dans une précédente cause, le Tribunal fédéral n'a compté que pour un seul, par rapport au minimum de cinq logements de comparaison, ceux qui dépendaient d'un seul bailleur (<ref-ruling> consid. 4c/aa p. 323). Ce jugement a été critiqué en considération de ce que l'<ref-law> n'exclut pas, d'après son texte, de retenir comme éléments de comparaison plusieurs logements appartenant au même bailleur, sinon dans l'hypothèse particulière où ce bailleur occupe une position dominante sur le marché (Raymond Bisang et al., Das schweizerische Mietrecht, 3e éd., Zurich 2008, no 21 ad <ref-law>; Patrick Blaser, La prise en considération des loyers usuels dans la fixation du loyer, Cahiers du bail, 2001, n° 2.7 p. 11). Selon une autre opinion, l'<ref-law> n'est pas en cause et l'approche du Tribunal fédéral se justifie, néanmoins, dans la mesure où la pratique d'un bailleur appliquée à plusieurs logements n'est pas représentative de ce qui est usuel sur le marché (Peter Higi, Commentaire zurichois, n° 83 ad <ref-law>). Pour le surplus, les auteurs sont défavorables à la proposition de ne compter que pour un seul, semblablement, les logements de bailleurs différents mais administrés par la même gérance (Bisang et al., Higi, ibid.; Blaser, op. cit., n° 2.5 p. 10; David Lachat, Le bail à loyer, 2008, n° 2.2.5 p. 460).
Dans la présente affaire, il ne se justifie pas d'étendre l'approche restrictive déjà adoptée par la Cour de céans, au sujet des logements de comparaison dépendant d'un seul bailleur, aux logements de bailleurs différents mais administrés par la même gérance. Sur ce point, le jugement de la Chambre des recours doit être confirmé.
2.4 Les demandeurs affirment que des six objets de comparaison retenus par cette autorité, aucun ne satisfait aux critères de l'<ref-law>. Selon leur exposé, par rapport à leur propre appartement, plusieurs ont une pièce de plus ou une surface nettement plus importante. L'un d'eux a une cheminée de salon. Certains ont une terrasse, voire une terrasse et un jardinet, alors que leur appartement n'a qu'un balcon. A leur avis, on ne peut pas comparer un logement datant de 1981 avec le leur qui est de vingt ans plus ancien. Plusieurs logements de comparaison se trouvent à plus d'un kilomètre et demi de distance, de sorte qu'ils n'appartiennent pas au quartier. Presque tous jouissent d'une situation tranquille, alors que leur appartement est exposé aux bruits d'une route à grand trafic et d'un chemin de fer.
Afin de contrôler les comparaisons retenues par la juridiction cantonale, le Tribunal fédéral a parfois complété l'état de fait de la décision attaquée, incomplet, sur la base du jugement de première instance (<ref-ruling> consid. 4b/ee p. 317). Dans la présente affaire, toutefois, aucune des deux décisions ne contient les indications nécessaires, puisque, en définitive, le Tribunal des baux n'a pas fait de comparaison et que la Chambre des recours s'est bornée à faire état de son « impression d'ensemble ». Le Tribunal fédéral n'est donc pas en mesure de se prononcer sur les critiques des demandeurs. Faute de contenir les motifs déterminants de fait, aux termes de l'<ref-law>, la décision attaquée doit être annulée en application de l'<ref-law>.
2.5 La Chambre des recours prendra elle-même une nouvelle décision qui décrira de façon précise les comparaisons effectuées pour établir les loyers usuels, ou elle renverra la cause au Tribunal des baux, selon le droit cantonal. Dans tous les cas, évidemment, on tiendra compte non seulement des loyers des logements de comparaison, mais aussi des frais accessoires respectivement inclus dans ces loyers ou perçus séparément par les bailleurs.
3. Compte tenue qu'aucune des parties n'obtient gain de cause, l'émolument judiciaire doit être réparti par moitié entre les demandeurs, d'une part, et la défenderesse, d'autre part, et les dépens seront compensés.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est partiellement admis, la décision attaquée est annulée et la cause est renvoyée au Tribunal cantonal pour nouvelle décision.
2. Les parties acquitteront un émolument judiciaire de 4'000 fr., à raison de 2'000 fr. à la charge des demandeurs et de 2'000 fr. à la charge de la défenderesse.
3. Il n'est pas alloué de dépens.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Vaud.
Lausanne, le 24 avril 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La présidente: Le greffier:
Klett Thélin