Faits:
A. Par contrat du 24 mai 1995, les époux H.A._ et F.A._ ont chargé la société X._ SA, de construire une villa familiale pour le prix forfaitaire de 445'000 fr. sur un bien-fonds de Saint-Légier-La-Chiésaz. Ils ont occupé ce logement dès le 14 mai 1996.
Le 9 juin 1997, les parties ont dressé par écrit la liste des retouches qui restaient à exécuter. En ce qui concerne les installations sanitaires, l'entreprise sous-traitante qui les avait réalisées, Z._ SA, devait surtout « livrer un mode d'emploi en français de la chaudière et régler le débit d'eau chaude et froide du lavabo de la salle de bain ».
Par lettre du 26 mai 2002, les maîtres de l'ouvrage se sont adressés à leur cocontractante pour exiger la réparation de divers défauts; ils faisaient notamment valoir que « depuis le début, l'eau de la salle de bain et de la douche (attenante à la chambre des parents) est orange ». A ce sujet, on effectua des investigations qui révélèrent la présence anormale, dans l'eau, d'oxyde de fer et de limon, provenant des installations intérieures du bâtiment.
Les maîtres de l'ouvrage ont exigé de X._ SA le remplacement de toute la tuyauterie. Une réunion s'est tenue le 19 juillet 2005 avec, en particulier, les maîtres de l'ouvrage et leur conseil, et les représentants de X._ SA et de Z._ SA. Cette dernière a alors promis d'exécuter divers travaux destinés à remédier à la pollution de l'eau; si nécessaire, ces travaux comprendraient le remplacement des tuyaux de distribution intérieure à partir de la nourrice. L'entreprise devait intervenir « à ses propres frais, respectivement à ceux de X._ SA, selon des modalités à convenir entre elles ». Par la suite, sans succès, les maîtres de l'ouvrage ont plusieurs fois sommé Z._ SA d'exécuter le remplacement de la tuyauterie.
B. Le 15 mai 2006, les maîtres de l'ouvrage ont cité X._ SA en conciliation devant le Juge de commune compétent. Le 21 août suivant, ils ont ouvert action contre elle devant le Juge de district de Monthey. La défenderesse devait être condamnée à exécuter le remplacement de la tuyauterie, sous menace des peines prévues par l'<ref-law> en cas d'insoumission aux décisions de l'autorité. A défaut, les demandeurs devaient être autorisés à faire accomplir cette opération par un tiers, aux frais de la défenderesse; celle-ci serait alors condamnée à verser une avance au montant de 30'000 francs. Dans tous les cas, la défenderesse devait être condamnée à payer les sommes de 17'992 fr.40 et 6'502 fr.70, « avec frais et accessoire », à titre de dommages-intérêts.
La défenderesse a conclu au rejet de l'action; elle a notamment excipé de la prescription.
Après instruction de la cause, celle-ci fut transmise pour jugement à la Ire Cour civile du Tribunal cantonal. Cette autorité s'est prononcée le 28 avril 2009; elle a rejeté l'action. Selon sa décision, l'ouvrage fourni par la défenderesse présente un défaut dont la conséquence est la pollution de l'eau; les demandeurs n'ont cependant pas, en temps utile, donné avis de ce défaut à l'autre partie, de sorte que leurs prétentions consécutives audit défaut se sont éteintes; au surplus, la prescription leur est de toute manière opposable.
C. 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 juridiction cantonale.
La défenderesse conclut au rejet du recours.

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 excède le minimum légal de 30'000 fr. (art. 51 al. 1 let. a et 74 al. 1 let. b LTF). 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). Il conduit son raisonnement juridique sur la base des faits constatés dans la décision attaquée (<ref-law>).
2. Il est constant que les parties se sont liées par un contrat d'entreprise et que la défenderesse a réalisé, en exécution de ce contrat, un ouvrage dont les demandeurs ont fait usage dès le 14 mai 1996.
Aux termes des art. 367 al. 1 et 370 CO, le maître doit vérifier l'état de l'ouvrage dont il a reçu livraison, cela aussitôt qu'il le peut d'après la marche habituelle des affaires, et, s'il y a lieu, en signaler les défauts à l'entrepreneur (art. 367 al. 1). Si le maître omet la vérification ou l'avis, il est censé avoir accepté l'ouvrage avec les défauts qu'il aurait pu constater et signaler (art. 370 al. 2). Si des défauts ne se manifestent que plus tard, le maître doit les signaler aussitôt qu'il en a connaissance; sinon, l'ouvrage est tenu pour accepté avec eux également (art. 370 al. 3). L'entrepreneur est déchargé de toute responsabilité en raison des défauts acceptés (art. 370 al. 1); par suite des autres défauts, régulièrement signalés, le maître peut exercer les droits qui lui sont conférés par l'<ref-law>. Le maître peut notamment exiger la réparation de l'ouvrage aux frais de l'entrepreneur, si la réparation est possible sans dépense excessive, et de plus, il peut réclamer des dommages-intérêts si l'entrepreneur est en faute (<ref-law>).
3. A teneur de l'<ref-law>, les droits du maître en raison des défauts de l'ouvrage, s'il s'agit d'une construction immobilière, se prescrivent par cinq ans à compter de la réception. En l'espèce, ce délai a couru au plus tard dès le jour où les demandeurs ont effectivement occupé le bâtiment réalisé; contrairement à leur opinion, il importe peu que la défenderesse ne leur ait pas formellement signifié l'achèvement de cette construction, et il importe tout aussi peu que celle-ci présentât de nombreux et importants défauts (<ref-ruling> consid. 4 p. 458). Faute d'interruption selon l'<ref-law>, le délai est donc arrivé à échéance en mai 2001, en ce qui concerne la réparation du défaut à l'origine de la pollution de l'eau, et depuis, la prescription est acquise à la défenderesse.
Le débiteur d'une obligation prescrite peut valablement renoncer à se prévaloir de la prescription acquise; il peut, en particulier, reconnaître la dette et promettre simultanément qu'il n'invoquera pas la prescription (Silvia Tevini Du Pasquier, in Commentaire romand, 2003, n° 9 ad <ref-law>; cf. <ref-ruling> consid. 3.3.7 in fine p. 240). En revanche, s'il reconnaît la dette sans renoncer explicitement ni tacitement à la prescription, le débiteur conserve le droit de s'en prévaloir car, à elle seule, si elle ne comporte pas une convention spécifique sur ce point, la reconnaissance n'apporte aucune modification à l'obligation reconnue et elle n'empêche pas le débiteur de soulever toutes les objections et exceptions qui lui appartenaient déjà (Tevini Du Pasquier, op. cit, nos 7 et 8 ad <ref-law>; <ref-ruling> consid. 3.2 p. 272). Si le débiteur reconnaît une obligation qui n'est pas encore prescrite, la reconnaissance interrompt la prescription et fait courir un nouveau délai par l'effet de l'<ref-law>.
Les demandeurs soutiennent que leur cocontractante a renoncé à la prescription en leur transmettant, en juillet 2005, une proposition de Z._ SA relative au remplacement de la tuyauterie, puis en participant à la réunion du 18 du même mois. Tout au plus, en entrant en matière sur les réclamations des demandeurs et en s'entremettant entre ceux-ci et la société tierce a qui elle avait sous-traité les installations sanitaires, la défenderesse a peut-être reconnu qu'elle assumait en principe l'obligation de remédier au défaut provoquant la pollution de l'eau. S'il en est ainsi, elle a alors tacitement renoncé à se prévaloir d'un éventuel retard dans l'avis des défauts nécessaire selon l'<ref-law> (cf. François Chaix, in Commentaire romand, n° 24 ad <ref-law>). Mais, dans les déclarations et le comportement de la défenderesse, rien ne peut être compris de bonne foi, selon le principe de la confiance qui régit l'interprétation des manifestations de volonté (<ref-ruling> consid. 4 p. 27/28), comme une promesse de remédier au défaut aussi dans l'hypothèse particulière où l'obligation correspondante se trouverait déjà atteinte par la prescription. En effet, les pourparlers auxquels la défenderesse a pris part n'ont comporté aucune allusion au problème juridique de la prescription, et, comme les demandeurs le soulignent, leur adverse partie ne s'est pas exprimée à ce sujet. On ne voit d'ailleurs pas pourquoi ni dans quel intérêt elle aurait renoncé à l'exception concernée. La prétention élevée contre elle reste donc atteinte par la prescription.
4. Selon l'<ref-law>, le juge ne peut pas suppléer d'office le moyen résultant de la prescription. La défenderesse ayant elle-même, dans le procès, soulevé ce moyen, les demandeurs invoquent vainement cette disposition. Enfin, il n'est pas nécessaire d'examiner l'argumentation qu'ils développent pour contester leur retard dans l'avis des défauts.
5. Le recours se révèle privé de fondement, ce qui conduit à son rejet. A titre de parties qui succombent, ses auteurs doivent acquitter l'émolument à percevoir par le Tribunal fédéral et les dépens auxquels l'autre partie peut prétendre.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les demandeurs acquitteront un émolument judiciaire de 2'500 francs.
3. Les demandeurs verseront une indemnité de 3'000 fr. à la défenderesse, à titre de dépens.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais.
Lausanne, le 12 août 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La présidente: Le greffier:
Klett Thélin