Faits:
A. Depuis près de quinze ans, A._ est active dans le domaine du placement de personnel fixe ou temporaire, qui est aussi celui des sociétés X._ SA, Y._ SA et Z._ SA. Elle a travaillé au service de cette première société jusqu'au mois de février 2004; elle avait souscrit une clause de prohibition de faire concurrence à l'employeuse, après la fin de son emploi, dont elle fut alors libérée à condition de ne pas débaucher, durant deux ans, les travailleurs intérimaires habituellement inscrits auprès de celle-ci.
A._ a décliné une offre d'emploi de Y._ SA relative à la direction de l'agence de cette société à Martigny; elle préférait entrer au service de Z._ SA, dès le 1er mars 2004, en qualité de responsable d'une agence nouvellement créée à Sion. Son salaire mensuel brut, payable treize fois par an, s'élevait à 6'000 fr.; il s'y ajoutait une indemnité mensuelle de 500 francs. Le contrat comportait une clause de prohibition de concurrence qui s'appliquerait « sur le territoire du canton du Valais et des cantons limitrophes » pour une durée de deux ans dès l'expiration des rapports de travail. En cas de contravention, l'ancienne responsable d'agence serait débitrice d'une peine conventionnelle égale à la rémunération brute perçue durant les six derniers mois de travail; elle serait en outre tenue de réparer le dommage qui excéderait ce montant.
Le 4 novembre 2005, la responsable d'agence a résilié son contrat de travail avec effet au 28 février 2006. Elle a expliqué, oralement, vouloir se reconvertir dans le secteur immobilier. Le 19 octobre, toutefois, elle avait conclu un contrat de travail avec Y._ SA, pour prendre la direction, dès le 1er mars 2006, d'une nouvelle agence de cette société-ci à Sion. Elle était consciente d'agir contrairement à la clause de prohibition de concurrence qui la liait à Z._ SA; dans ses pourparlers avec Y._ SA, il fut envisagé que cette dernière contribuerait au paiement d'une éventuelle peine conventionnelle. Le contrat conclu avec cette nouvelle employeuse comportait lui aussi, d'ailleurs, une clause de prohibition de concurrence, avec une peine conventionnelle au montant de 50'000 francs. Le salaire mensuel brut, payable treize fois par an, était fixé à 8'000 francs.
B. Z._ SA a entrepris une poursuite pour dette contre A._ et lui a fait notifier un commandement de payer au montant de 36'000 fr., avec intérêts au taux de 5% par an dès le 23 mars 2006, à titre de peine conventionnelle. Le 25 septembre 2006, elle a obtenu du juge compétent la mainlevée provisoire de l'opposition au commandement de payer.
Le 20 octobre 2006, devant le Juge de district de Martigny, A._ a ouvert action en libération de dette contre Z._ SA; elle contestait entièrement la prétention de la défenderesse. Celle-ci a conclu au rejet de l'action et à la mainlevée définitive de l'opposition au commandement de payer.
Après clôture de l'instruction, la cause fut transmise à la IIe Cour civile du Tribunal cantonal. Cette autorité a statué le 9 février 2009; elle a rejeté l'action et prononcé que la mainlevée de l'opposition devenait définitive.
C. Agissant par la voie du recours en matière civile, la demanderesse requiert le Tribunal fédéral de réformer le jugement en constatant qu'elle n'est pas débitrice du montant de 36'000 fr., en capital, réclamé par la défenderesse.
Celle-ci conclut au rejet du recours.

Considérant en droit:
1. Le recours est dirigé contre un jugement final (art. 90 LTF), rendu en matière civile (art. 72 al. 1 LTF) et en dernière instance cantonale (art. 75 al. 1 LTF). Son auteur a pris part à l'instance précédente et succombé dans ses conclusions (art. 76 al. 1 LTF). La valeur litigieuse excède le minimum légal de 15'000 fr. prévu en matière de droit du travail (art. 51 al. 1 let. a et 74 al. 1 let. a LTF). Introduit en temps utile (art. 100 al. 1 LTF) 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 (art. 95 let. a LTF). Le Tribunal fédéral applique ce droit d'office, hormis les droits fondamentaux (art. 106 LTF). 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 (art. 42 al. 2 LTF; <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 (art. 106 al. 2 LTF; <ref-ruling> consid. 3.2 p. 88; <ref-ruling> consid. 2.2 p. 246; <ref-ruling> consid. 1.4.2). En règle générale, il conduit son raisonnement juridique sur la base des faits constatés dans la décision attaquée (art. 105 al. 1 LTF).
2. Il est constant que les parties se sont liées par un contrat de travail, conclu par écrit le 12 février 2004, et que ce contrat comportait une clause interdisant à la demanderesse de faire concurrence à la défenderesse après la fin des rapports de travail.
Les parties ont donc observé la forme écrite nécessaire à la validité d'une clause de ce genre, selon l'art. 340 al. 1 CO. La demanderesse soutient vainement que cela n'était pas suffisant et qu'en raison de son importance particulière, la prohibition de concurrence aurait dû être mise en évidence dans le contrat, par un procédé visuel, ou contresignée spécialement par la partie qui hypothéquait sa liberté économique. Cette exigence est étrangère à la disposition précitée. Au demeurant, la demanderesse ne saurait prétendre avoir signé le contrat en ignorant ou en sous-estimant la portée de la clause concernée: quelques jours auparavant, le 5 février 2004, elle avait dû négocier la caducité d'une clause semblable qui la liait à sa précédente employeuse.
3. Aux termes de l'art. 340a al. 1 CO, la prohibition de concurrence doit être limitée convenablement quant au lieu, au temps et au genre d'affaires, de façon à ne pas compromettre l'avenir économique du travailleur contrairement à l'équité. La demanderesse affirme que l'autre partie exerce ses activités de placement de personnel en Suisse romande seulement, et que la prohibition convenue pour « le territoire du canton du Valais et des cantons limitrophes » est donc excessive en tant qu'elle inclut le Haut-Valais et les cantons de Berne, d'Uri et du Tessin; il en résulte, selon l'argumentation présentée, que la prohibition est dépourvue de toute validité. Or, l'art. 340a al. 2 CO prévoit textuellement qu'une prohibition excessive doit être réduite par le juge, selon sa libre appréciation et en tenant compte de toutes les circonstances. En l'occurrence, la défenderesse peut légitimement exiger, de son ancienne responsable d'agence, qu'elle s'abstienne de lui faire concurrence dans la région sédunoise. La prohibition n'est pas non plus excessive en raison de l'âge de la demanderesse - soixante-et-un ans actuellement - et du temps pendant lequel elle a pratiqué l'activité de placement de personnel.
4. Aux termes de l'art. 340c al. 2 CO, une prohibition de faire concurrence cesse si le travailleur résilie le contrat de travail pour un motif justifié et imputable à l'employeur.
La demanderesse a allégué divers motifs d'insatisfaction qui justifiaient, prétendument, sa volonté de changer d'employeuse: elle avait demandé sans succès que la responsabilité du suivi des débiteurs de l'agence lui fût transférée; les objectifs imposés par la défenderesse étaient irréalistes et nécessitaient l'accomplissement de nombreuses heures supplémentaires; en outre, la demanderesse ne parvenait pas à obtenir un quatorzième salaire. Selon le jugement de la Cour civile, aucun de ces motifs n'est suffisamment grave; il s'agit plutôt de simples prétextes avancés « pour les besoins de la cause », compte tenu que la demanderesse a résilié le contrat de travail sans faire aucun reproche à l'employeuse, et en lui en expliquant qu'elle allait se reconvertir dans le secteur immobilier.
En instance fédérale, la demanderesse persiste dans sa propre thèse et elle critique le jugement précité, où il est difficile de discerner ce qui relève de la constatation des faits, d'une part, et de l'appréciation juridique des faits constatés, d'autre part.
On ne saurait exclure que le congé donné par le travailleur puisse être fondé sur plusieurs motifs, tous imputables à l'employeur, et que ceux-ci soient propres à entraîner l'extinction de la prohibition de concurrence en raison de leur concours, alors qu'aucun d'eux ne serait, à lui seul, suffisamment important au regard de l'art. 340c al. 2 CO (cf. <ref-ruling> consid. 2.2.1 p. 359). Il n'est pas d'emblée exclu, non plus, que dans le procès relatif la prohibition de concurrence, le travailleur puisse utilement invoquer des motifs de congé qu'il n'aurait, jusque là, jamais communiqués à l'autre partie (cf. Ullin Streiff et Adrian von Kaenel, Arbeitsvertrag, 6e éd., Zurich 2006, n° 9 ad art. 340c CO). Mais en l'espèce, il est constaté que la demanderesse a conclu un nouveau contrat de travail en étant consciente qu'elle enfreindrait la prohibition de concurrence, qu'elle a résilié le contrat en cours sans adresser aucun reproche à l'employeuse, et qu'elle lui a mensongèrement déclaré vouloir se reconvertir dans un autre secteur d'activité. Au regard de cette situation particulière, le moyen tiré de l'art. 340c al. 2 CO peut être rejeté sans plus de discussion et il n'est pas nécessaire d'effectuer une analyse approfondie des conditions de travail au service de cette employeuse.
5. Aux termes de l'art. 163 al. 3 CO, le juge doit réduire les peines conventionnelles qu'il estime excessives. Son intervention ne se justifie, toutefois, que si le montant fixé dépasse toute mesure raisonnable et compatible avec le droit et l'équité. Tel est le cas, notamment, lorsqu'il existe une disproportion évidente entre le montant convenu et l'intérêt du créancier à élever la totalité de sa prétention. Les circonstances de l'espèce sont déterminantes; il convient de tenir compte, en particulier, de la nature et de la durée du contrat, de la gravité de la faute, de la situation économique des parties et de leur expérience en affaires. Il n'incombe pas au créancier de prouver que la peine convenue est appropriée, mais au débiteur d'alléguer et d'établir des faits propres à justifier une réduction (<ref-ruling> consid. 5.2 p. 209).
La demanderesse allègue que l'agence placée sous sa responsabilité est « partie de zéro » lors de son engagement et qu'elle y a été « exploitée ». Le chiffre d'affaires de l'agence à considérablement diminué après son passage à Y._ SA mais cette régression est surtout imputable, prétend-elle, « à l'inexpérience [et] au manque d'engagement de la personne qui lui a succédé ». Rien de cela n'est très consistant; sur la base des constatations cantonales, on observe plutôt que la demanderesse a montré une absence totale de scrupules pour entreprendre, en violation flagrante de ses engagements contractuels, de concurrencer la défenderesse précisément sur le marché local que celle-ci lui avait confié. En février 2004, elle avait souscrit la prohibition de concurrence en parfaite connaissance de l'enjeu d'une pareille clause, tant pour elle-même que pour l'autre partie. Il ne s'impose donc pas, dans ces conditions, de réduire la pénalité convenue.
6. Le recours se révèle privé de fondement, ce qui conduit à son rejet. A titre de partie qui succombe, son auteur doit 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. La demanderesse acquittera un émolument judiciaire de 2'000 francs.
3. La demanderesse versera à la défenderesse, à titre de dépens, une indemnité de 2'500 francs.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais.
Lausanne, le 12 juin 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La présidente: Le greffier:
Klett Thélin