Faits:
A. Dès le 1er septembre 1997, les frères A.X._ et B.X._ ont pris à bail des locaux commerciaux sis au rez-de-chaussée et au sous-sol d'un bâtiment de Genève, destinés à l'exploitation d'un café-restaurant. Depuis le 1er septembre 2001, le loyer annuel s'élève à 42'000 fr. Le contrat comporte notamment les clauses ci-après:
Il est spécifié qu'un compteur d'eau est installé au café. Un relevé concernant les dépenses d'eau sera effectué annuellement et les frais seront à la charge des locataires.
Les locataires prendront à leur charge tout contrat relatif à l'hygiène de l'établissement, notamment la désinsectisation et la dératisation des locaux loués.
La bailleresse est la société anonyme Y._ SA. Les locataires se refusant de manière répétitive à lui rembourser des frais de consommation d'eau et de désinsectisation, elle leur a adressé des sommations avec menace de résilier le bail, le 23 décembre 2003, le 26 juillet 2005 et le 21 mars 2006.
La première sommation portait sur 984 fr. de consommation d'eau et 645 fr.60 pour l'intervention d'une entreprise de désinsectisation. Les locataires avaient reçu une photographie du compteur d'eau, celui-ci se trouvant dans un local auquel ils n'ont pas accès. Ils protestèrent au motif qu'ils n'avaient pas pu vérifier eux-mêmes ce compteur. Ils saisirent sans résultat l'autorité de conciliation en matière de baux et loyers, puis ils renoncèrent à agir en justice. Une correspondance se poursuivit au sujet de la facturation de l'eau.
La deuxième sommation portait sur 1'709 fr.70 de consommation d'eau et 645 fr.60 pour une nouvelle intervention de l'entreprise de désinsectisation.
La troisième sommation portait sur 541 fr. de consommation d'eau et 645 fr. 60 pour la même prestation de désinsectisation qui était demeurée impayée. Les locataires devaient s'acquitter dans le délai de trente jours dès réception de cette sommation, soit dès le 22 mars 2006. Ils annoncèrent qu'ils refuseraient de payer l'eau aussi longtemps que des relevés du compteur ne leur seraient pas remis, puis, le 22 avril 2006, ils émirent un ordre de virement au montant de 1'186 fr.60 en faveur de la bailleresse; celle-ci en fut créditée le 24 du même mois.
Le 12 mai 2006, usant d'une formule officielle, la bailleresse a résilié le bail avec effet au 30 juin suivant, au motif que les montants de 541 fr. et 645 fr. 60 n'avaient pas été intégralement versés dans le délai de la sommation.
B. Le 9 juin 2006, devant l'autorité de conciliation compétente puis devant le Tribunal des baux et loyers du canton de Genève, les locataires ont ouvert action contre la bailleresse; leur demande tendait à l'annulation de la résiliation du bail. La défenderesse s'est opposée à cette demande et elle a pris des conclusions reconventionnelles tendant à l'évacuation des locaux loués.
Le tribunal s'est prononcé le 2 octobre 2007; il a constaté la validité de la résiliation et condamné les demandeurs à évacuer immédiatement les locaux loués.
Statuant le 16 juin 2008 sur l'appel des demandeurs, la Chambre d'appel en matière de baux et loyers a confirmé ce jugement.
C. Agissant par la voie du recours en matière civile, les demandeurs requièrent le Tribunal fédéral de réformer l'arrêt de la Chambre d'appel en ce sens que la résiliation du bail communiquée le 12 mai 2006 soit annulée.
La défenderesse conclut principalement à l'irrecevabilité du recours, subsidiairement à son rejet.

Considérant en droit:
1. Dans une contestation concernant la validité d'une résiliation de bail, selon la jurisprudence pertinente pour l'application des art. 51 al. 1 let. a, 51 al. 2 et 74 al. 1 let. a LTF, la valeur litigieuse est égale au loyer de la période minimum pendant laquelle le contrat subsiste si la résiliation n'est pas valable, période qui s'étend jusqu'à la date pour laquelle un nouveau congé peut être donné; il faut prendre ici en considération la période de protection de trois ans, à compter dès la fin de la procédure judiciaire, qui est prévue par l'art. 271a al. 1 let. e CO (<ref-ruling> consid. 1 p. 386; voir aussi <ref-ruling> consid. 1 p. 149). En l'espèce, le loyer d'une seule année excède la valeur litigieuse minimale qui est fixée à 15'000 francs.
Pour le surplus, 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>). Il est formé par une partie qui a pris part à l'instance précédente et succombé dans ses conclusions (<ref-law>). Contrairement à l'opinion de la défenderesse, les conclusions et la motivation présentées satisfont aux exigences de l'art. 42 al. 1 et 2 LTF. Introduit en temps utile (<ref-law>), le recours est en principe recevable.
Le recours peut être exercé 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 conformément aux exigences légales relatives à la motivation du recours (<ref-law>; <ref-ruling> consid. 1.4.1 p. 254). 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 de bail à loyer aux termes de l'<ref-law>.
Selon l'<ref-law>, lorsque le locataire, après réception de la chose, a du retard pour s'acquitter d'un terme ou de frais accessoires échus, le bailleur peut lui fixer par écrit un délai de paiement et lui signifier qu'à défaut de paiement dans ce délai, il résiliera le bail. Le délai doit être d'au moins trente jours pour les baux d'habitation ou de locaux commerciaux. L'<ref-law> dispose qu'à défaut de paiement dans le délai fixé, le bailleur peut résilier le contrat avec effet immédiat; les baux d'habitation ou de locaux commerciaux peuvent être résiliés avec un délai de congé minimum de trente jours pour la fin d'un mois.
3. La validité d'une résiliation fondée sur l'<ref-law> suppose, entre autres conditions, que le locataire se soit effectivement trouvé en retard dans le paiement du loyer ou de frais accessoires lorsque la sommation prévue à l'<ref-law> lui a été adressée (Raymond Bisang et al., Das schweizerische Mietrecht, 3e éd., 2008, n° 14 ad <ref-law>). En l'occurrence, la juridiction cantonale a retenu qu'un montant total de 1'186 fr.60 était dû à la défenderesse à titre de frais accessoires, comprenant 541 fr. de consommation d'eau et 645 fr. 60 de frais de désinsectisation.
Les demandeurs font valoir que l'adverse partie n'a apporté aucune preuve au sujet de la consommation d'eau et que les juges retiennent ce montant de 541 fr. sur la base de simples allégations, pourtant contestées par eux, de cette même partie. Dans les deux instances cantonales, ils ont réclamé sans succès que le fonctionnement du compteur d'eau fût vérifié. Ils invoquent l'<ref-law> qui répartit le fardeau de la preuve dans les contestations soumises au droit civil fédéral; cette disposition est violée, en particulier, lorsque le juge constate un fait important pour l'application du droit alors que ce fait est contesté et qu'aucune preuve n'a été administrée (<ref-ruling> consid. 7.1 p. 299; <ref-ruling> consid. 5.4 p. 601).
A première vue, il incombait à la défenderesse d'alléguer et de prouver la quantité d'eau consommée par le café-restaurant, en tant que le montant des frais accessoires prétendument exigibles, objet de la sommation du 21 mars 2006, dépendait de cette quantité. Or, celle-ci n'a pas été prouvée et la Chambre d'appel n'a fait, non plus, aucune constatation ni aucune vérification du calcul aboutissant au montant de 541 fr. Le Tribunal fédéral peut néanmoins se dispenser d'examiner le moyen que les demandeurs prétendent tirer de l'<ref-law>, car de toute manière, il est incontesté que les frais de désinsectisation étaient dus par 645 fr.60, et que cette somme-ci n'a pas non plus été payée dans le délai de la sommation.
4. Selon l'<ref-law>, la résiliation du bail est annulable lorsqu'elle contrevient aux règles de la bonne foi. Les demandeurs ayant contesté la résiliation dans le délai et selon les modalités prévus par l'<ref-law>, ils peuvent réclamer, s'il y a lieu, la protection de cette disposition.
Selon la jurisprudence, la résiliation fondée sur l'<ref-law> n'est contraire aux règles de la bonne foi, et donc annulable sur la base de l'<ref-law>, que dans des circonstances particulières. L'annulation entre en considération lorsque le bailleur a réclamé au locataire, avec menace de résiliation du bail, une somme largement supérieure à celle en souffrance, alors qu'il n'était pas certain du montant effectivement dû (<ref-ruling> consid. 4b p. 33). L'annulation entre aussi en considération lorsque l'arriéré est insignifiant, ou lorsque ce montant a été réglé très peu de temps après l'expiration du délai comminatoire, alors que, auparavant, le locataire s'était toujours acquitté à temps du loyer, ou encore lorsque le bailleur ne résilie le contrat que longtemps après l'expiration de ce même délai (arrêt 4C.430/2004 du 8 février 2005, consid. 3.1 in SJ 2005 I p. 310/311).
Au regard de l'art. 77 al. 1 ch. 1 et 77 al. 2 CO, le délai comminatoire est échu le vendredi 21 avril 2006. Les demandeurs auraient dû agir de manière que le compte de la défenderesse fût crédité au plus tard à cette date (Bisang et al., op. cit., n° 30 ad <ref-law>; David Lachat, Le bail à loyer, 2008, p. 668 n° 2.2.3). La bonification est intervenue le lundi 24, soit le jour ouvrable suivant immédiatement. Néanmoins, les règles de la bonne foi n'autorisent pas les demandeurs à se prévaloir de cette circonstance car pendant tout le cours du délai, ils ont retenu le montant des frais de désinsectisation de manière inexcusable, sans aucune espèce de justification. Le montant de 645 fr.60 ne saurait être jugé insignifiant (<ref-ruling> consid. 4b in initio, déjà cité). Les demandeurs soulignent vainement que l'arriéré portait seulement sur des frais accessoires et qu'ils ont toujours acquitté régulièrement un loyer beaucoup plus important; il demeure que la défenderesse a dû plusieurs fois user de sommation pour obtenir certaines des prestations convenues.
La défenderesse a laissé écouler près de trois semaines entre l'expiration du délai comminatoire et la résiliation du bail. Cette inaction est longue et elle correspond probablement à la limite de ce qui peut être admis, au regard des règles de la bonne foi, comme exempt d'équivoque de la part du bailleur. Une inaction plus longue encore pourrait être comprise, sauf circonstances particulières, comme une renonciation à résilier le contrat (cf. Roger Weber, in Commentaire bâlois, 4e éd., 2007, n° 7 ad <ref-law>, avec références à d'autres auteurs; Bisang et al., op. cit., n° 34 ad <ref-law>, considérant une attente d'un mois comme normale). Dans la présente affaire, contrairement à l'opinion des demandeurs, la résiliation du 12 mai 2006 échappe à la censure de l'<ref-law>.
5. La résiliation a provoqué l'expiration du bail et celle-ci a fait naître, à la charge des demandeurs, l'obligation de restituer la chose louée conformément à l'<ref-law>. Il n'est pas contesté que la défenderesse puisse exiger, sur la base de cette disposition, l'évacuation des locaux.
6. Le recours se révèle privé de fondement, ce qui entraîne 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 3'000 francs.
3. Les demandeurs verseront, solidairement entre eux et à titre de dépens, une indemnité de 3'500 fr. à la défenderesse.
4. Le présent arrêt est communiqué aux parties et à la Chambre d'appel en matière de baux et loyers du canton de Genève.
Lausanne, le 25 novembre 2008
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
Le président: Le greffier:
Corboz Thélin