Faits: A. La société française Z._ Sàrl commercialise des spas, soit des baignoires ou bassins à bouillonnement et remous, avec pompage de l'eau en circuit fermé. En mars 2008, elle a tenu un stand à la foire lausannoise « Habitat et jardins ». Les époux H.X._ et F.X._ ont visité ce stand et ils y ont reçu un prospectus. Le 28 avril 2008, à l'issue de pourparlers téléphoniques lors desquels il avait discuté la prise en charge de certains frais, H.X._ a passé commande d'un spa de marque « Clearwater Spas », modèle « pro duo », couleur « carribean blue », au prix de 41'500 francs. Cet appareil devait être livré à Grimisuat. Le 16 mai, lors d'un nouvel appel téléphonique, H.X._ s'est enquis d'un appareil disponible sans délai de livraison. Il lui fut répondu qu'un appareil de couleur beige, alors en exposition à la foire de La Roche-sur-Foron, en France, pourrait être fourni dès la fin de cette manifestation. H.X._ a accepté cette proposition. Il a ensuite expliqué que la livraison du spa devait impérativement s'accomplir avant le montage de la charpente et de la toiture du local destiné à le recevoir, « tous les travaux [demeurant] en attente ». B. Le 4 juin 2008, Z._ Sàrl a livré un spa de couleur beige qui avait été exposé à la foire de La Roche-sur-Foron. Au moyen d'une grue, l'appareil fut placé dans un alvéole en béton préparé à cette fin. L'appareil comprenait un entourage en bois dont un élément était fendu. Par ailleurs, l'électricien alors présent refusa d'exécuter le raccordement au réseau parce que le boîtier de branchement ne correspondait pas aux normes appliquées en Suisse. Enfin, une notice d'utilisation manquait également. H.X._ a signé le bulletin de livraison. Il y a apporté des réserves relatives à l'élément fendu et à la notice manquante; la mise en service de l'appareil était « différée ». Le 11 juillet 2008, pour le compte de Z._ Sàrl, un technicien est venu mettre l'appareil en service; il a remplacé le boîtier de branchement électrique et une pompe de massage. Une expertise judiciaire a révélé plus tard que ce nouveau boîtier, certes conforme aux prescriptions de raccordement au réseau, n'offre pas une protection suffisante contre le risque d'électrocution. Le 14 du même mois, H.X._ s'est adressé à Z._ Sàrl pour élever de sévères critiques. Les vis des panneaux de protection du branchement électrique étaient « complètement usées », d'où il apparaissait que l'appareil livré avait servi « lors de nombreuses expositions » et n'était pas un modèle neuf comme « confirmé par vos soins lors de l'exposition de Lausanne ». Le filtre était « complètement encrassé » par suite de nombreuses utilisations et il en émanait une « puanteur conséquente ». Les bâches de protection et d'étanchéité étaient déchirées et le boîtier de l'écumeur ( skimmer ) était fissuré. L'appareil ne satisfaisait pas aux normes suisses et l'éclairage ne fonctionnait pas. Au choix de Z._ Sàrl, le client exigeait soit le remplacement de ce spa par un appareil neuf, soit le remboursement intégral des sommes payées et des frais de déchargement, soit le remplacement de trois cartouches d'ozone, du filtre et de toutes les pièces défectueuses qu'il avait mentionnées, avec un « abattement important » sur le prix. Z._ Sàrl a annoncé une prochaine intervention du technicien. Le 5 septembre 2008, celui-ci a remplacé deux filtres, trois ozonisateurs, la couverture, la « carte lumière » et les vis; il n'a pas pu réparer l'écumeur faute d'un accès suffisant. Il a constaté que la pompe avait fonctionné à vide, ce qui pouvait provoquer sa détérioration; il en a préconisé le remplacement. Le 8 septembre, H.X._ a derechef protesté auprès de Z._ Sàrl. Le spa n'avait fonctionné que deux jours; de plus, le filtre « côté jacuzzi », l'écumeur complet et la notice d'utilisation en français manquaient encore. Au choix du fournisseur, il réclamait soit une remise de trente pour cent ou 12'450 fr. sur le prix convenu, soit la livraison d'un spa neuf avec prise en charge de l'ensemble des frais. Z._ Sàrl a annoncé que le technicien se présenterait le 25 septembre pour remplacer un filtre, remplacer la pompe et réparer l'écumeur; elle refusait le remplacement complet de l'appareil. Le 19 septembre 2008, par l'intermédiaire d'un avocat, H.X._ a déclaré résoudre le contrat de vente au motif que l'appareil avait « déjà servi dans une foire commerciale » et qu'il ne fonctionnait pas. Il réclamait le remboursement de 43'440 francs. Z._ Sàrl était sommée de récupérer le spa à ses frais. H.X._ précisait que les fenêtres de sa villa seraient installées « début octobre » et que l'évacuation de l'appareil serait ensuite « beaucoup plus difficile et plus chère ». H.X._ n'a pas donné son accord à l'intervention prévue le 25 septembre 2008; celle-ci n'a pas été exécutée. H.X._ avait payé 35'000 fr. à la livraison du spa et 3'250 fr. à la mise en service, soit 38'250 fr. au total. C. Le 1er décembre 2008, H.X._ et F.X._ ont conjointement ouvert action contre Z._ Sàrl devant le Juge de district de Sion. Selon leurs conclusions plus tard complétées, la défenderesse devait être condamnée à rembourser 38'250 fr. avec intérêts au taux de 5% par an dès le 19 septembre 2008; le tribunal devait lui donner acte de ce que « le spa litigieux peut être repris ». La défenderesse a conclu au rejet de l'action. Le Juge de district a fait accomplir l'expertise déjà mentionnée puis il s'est prononcé le 30 janvier 2012; il a accueilli l'action et condamné la défenderesse selon les conclusions de la demande. Il lui a imparti un délai de soixante jours pour reprendre le spa au domicile des demandeurs. La IIe Cour civile du Tribunal cantonal a statué le 21 mars 2013 sur l'appel de la défenderesse. Elle a accueilli l'appel et rejeté l'action. D. Agissant par la voie du recours en matière civile, les demandeurs saisissent le Tribunal fédéral de conclusions identiques à celles déjà prises devant le Juge de district. La défenderesse conclut au rejet du recours.