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'art. 292 CP 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. 