Faits:
A. Le 20 juin 2007, Y._ SA a engagé X._ en qualité de consultant informatique, dès le 1er juillet suivant, pour une mission à accomplir au service de la banque O._ SA à Genève. Le salaire mensuel, payable douze fois par an, était fixé à 9'170 francs. La durée du contrat était indéterminée mais il était prévu qu'après six mois, X._ pourrait être engagé directement par la banque. Le contrat écrit comportait une clause ainsi libellée:
Le collaborateur s'engage à ne pas accepter un poste ou une mission directement ou par l'intermédiaire d'une autre société de services au sein des entreprises de mission pour lesquelles il est intervenu au nom de Y._ SA. Cette interdiction est valable pendant la durée du contrat. [En cas de violation, l'employeuse pourra réclamer] une indemnité forfaitaire équivalant à trois mois de salaire.
Le 26 novembre 2007, l'employeuse a résilié le contrat avec effet au 31 décembre suivant; elle indiquait au travailleur que « cette mesure est prise afin de vous permettre d'être engagé par notre client, la banque O._ SA, dès le 1er janvier 2008 ».
Ayant appris que X._ ne serait pas engagé par la banque mais que, néanmoins, il resterait à son service jusqu'au 31 mars 2008, l'employeuse interpella cette dernière pour savoir si, « dans un premier temps », elle souhaitait prolonger l'engagement par son intermédiaire. La cliente répondit que selon les dires du consultant, celui-ci se ferait engager par l'intermédiaire d'une autre société. L'employeuse ayant aussi interpellé X._, celui-ci rappela qu'un désaccord s'était élevé au sujet du décompte des jours de vacances; pour le surplus, il répondit ainsi: « Dans la mesure où je vous confirme que je n'accepterai et ne signerai aucun contrat avant le 1er janvier 2008, je suis en parfait accord avec la clause de non-sollicitation du contrat signé avec Y._ SA ».
X._ fut engagé par Z._ SA; sa mission de consultant informatique, à accomplir au service de la banque O._ SA dès le 1er janvier 2008, devait durer trois mois. L'administrateur de cette nouvelle employeuse signa un exemplaire du contrat le 15 décembre 2007; X._ signa un autre exemplaire le 2 janvier 2008 et il le restitua quelques temps après; dans l'intervalle, il avait poursuivi son activité au service de la banque.
B. Le 23 janvier 2008, X._ a ouvert action contre Y._ SA devant le Tribunal de prud'hommes du canton de Genève. La défenderesse devait être condamnée à payer 9'170 fr. à titre de salaire brut pour le mois de décembre 2007, et 421 fr.60 à titre d'indemnité nette pour un jour de vacances non pris. Ces sommes devaient porter intérêts au taux de 5% par an dès le 25 décembre 2007.
La défenderesse a reconnu devoir 4'890 fr.75 et elle a conclu, pour le surplus, au rejet de l'action. Elle a introduit une action reconventionnelle: le demandeur devait payer une « indemnité forfaitaire » correspondant à trois mois de salaire, soit 22'619 fr.25 après compensation de son dû, des dommages-intérêts au montant de 47'665 fr.20, et des intérêts au taux de 5% par an dès le 1er janvier 2008.
Le tribunal s'est prononcé le 2 octobre 2008. Il a accueilli l'action principale, à ceci près que le cours des intérêts commençait le 31 décembre 2007 seulement; il a rejeté l'action reconventionnelle.
La défenderesse a appelé du jugement; sans plus résister à l'action principale, elle persistait dans l'action reconventionnelle. La Cour d'appel a statué le 25 mars 2009. En définitive, le demandeur se trouve condamné à payer une indemnité réduite à deux mois de salaire, soit 18'340 fr.; le montant de l'action principale, soit 9'591 fr.60, dû à titre de salaire brut et soumis aux déductions sociales, doit être déduit, et le solde porte intérêts au taux de 5% par an dès le 1er janvier 2008.
C. Agissant par la voie du recours en matière civile, le demandeur requiert le Tribunal fédéral de réformer l'arrêt de la Cour d'appel en ce sens que l'action reconventionnelle soit entièrement rejetée.
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>). Son auteur a pris part à l'instance précédente et succombé dans ses conclusions (<ref-law>). 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 (<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).
Le Tribunal fédéral doit conduire son raisonnement juridique sur la base des faits constatés dans la décision attaquée (<ref-law>); en règle générale, les allégations de fait et les moyens de preuve nouveaux sont irrecevables (<ref-law>). Le tribunal peut compléter ou rectifier même d'office les constatations de fait qui se révèlent manifestement inexactes, c'est-à-dire arbitraires aux termes de l'art. 9 Cst. (<ref-ruling> consid. 1.1.2 p. 252), ou établies en violation du droit (<ref-law>). La partie recourante est autorisée à attaquer des constatations de fait ainsi irrégulières si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>).
2. Il est constant que les parties se sont liées par un contrat de travail, pour le compte d'une entreprise tierce, locataire de services, et que ce contrat comportait une clause restreignant le droit du demandeur de conclure, pendant sa durée, un contrat semblable avec une entreprise concurrente de la défenderesse. Il est également constant que le contrat des parties, résilié par la défenderesse, a pris fin le 31 décembre 2007. Le demandeur prétend n'avoir conclu un nouveau contrat, avec Z._ SA, qu'après cette date seulement, et que par conséquent, il n'est pas débiteur de l'« indemnité forfaitaire » prévue par ladite clause.
Selon son argumentation, l'art. 19 al. 1 de la loi fédérale sur le service de l'emploi et la location de services (LSE; RS 823.11) était applicable et cette disposition exigeait que le contrat de travail avec Z._ SA fût conclu par écrit; de plus, lui-même et cette société ont convenu, ainsi que le permettait l'<ref-law>, de donner la forme écrite audit contrat. Cette forme n'a pas été observée avant qu'il eût lui-même signé ce contrat et remis l'exemplaire signé à la nouvelle employeuse; or, il n'a accompli ces actes qu'en janvier 2008, soit après la fin de son contrat avec la défenderesse.
L'art. 19 al. 3 LSE règle les conséquences, dans le contexte spécifique de la location de services, d'un éventuel vice de forme du contrat de travail. De cette disposition et de l'<ref-law>, il ressort qu'un contrat tacite ou oral est néanmoins valable; seul son contenu est éventuellement modifié en faveur du travailleur. Quant à la portée de la forme écrite convenue selon l'<ref-law>, on observe qu'immédiatement après le 31 décembre 2007, le demandeur n'a pas cessé de travailler au motif que le contrat n'était pas dûment signé; au contraire, il a fourni sans interruption l'activité attendue par Z._ SA et par la banque O._ SA.
Selon les constatations de la Cour d'appel, cette dernière savait déjà, à fin novembre 2007 et par le demandeur, que celui-ci se ferait engager par une société de services autre que la défenderesse pour continuer son activité commencée en juillet de la même année. Les pourparlers entre le demandeur et Z._ SA ont abouti, au plus tard, le 15 décembre 2007; ensuite, seule la signature du contrat écrit, de la main du demandeur, est restée en suspens. Au regard de ces éléments, il est indéniable que l'activité fournie par le demandeur après le 31 décembre 2007, sans interruption, reposait sur un accord antérieur à cette date, et que cet accord n'était rien d'autre qu'un contrat de travail aux termes de l'<ref-law>. Le demandeur argue vainement de la date postérieure à laquelle il a enfin signé le contrat écrit, avant de le restituer.
3. L'interdiction contractuelle de se faire engager par une société de services concurrente, souscrite par le demandeur en juin 2007, est une restriction de la liberté économique de ce travailleur, de sorte qu'elle est soumise aux dispositions légales applicables aux clauses de prohibition de faire concurrence à l'employeur (<ref-ruling> consid. 2.1.1 p. 355). Le demandeur se prétend libéré par l'effet de l'<ref-law>, selon lequel la prohibition de concurrence cesse si l'employeur résilie le contrat sans que le travailleur ne lui ait donné un motif justifié; il affirme n'avoir aucunement provoqué la résiliation que la défenderesse lui a signifiée le 26 novembre 2007.
Selon la Cour d'appel, les parties ont d'emblée convenu, en juin 2007, que l'engagement du demandeur par l'intermédiaire de la défenderesse durerait six mois, et que le demandeur pourrait ensuite se faire engager directement par la banque cliente. La lettre de résiliation faisait d'ailleurs référence à ce projet d'engagement direct par la banque. Le demandeur souligne qu'au cours du mois de janvier 2008, il espérait encore obtenir cet engagement direct. La résiliation du 26 novembre 2007 s'inscrivait donc exactement dans ce qui était convenu dès le début entre les parties. Au regard de cette situation particulière, bien que la défenderesse ait résilié le contrat, le demandeur ne peut pas invoquer utilement l'<ref-law>.
Le demandeur invoque l'art. 9 Cst. et se plaint, en rapport avec la résiliation du contrat, d'une constatation arbitraire de divers faits, mais il ne met pas en doute que les parties aient d'emblée convenu d'un engagement initial limité à six mois. Il ne prétend pas non plus que la défenderesse, ayant appris que l'engagement direct souhaité par le demandeur ne se réalisait pas, aurait refusé de le réengager elle-même. Sa critique de la constatation des faits n'a donc pas d'incidence sur l'issue de la cause.
4. L' « indemnité forfaitaire » promise en cas de violation de l'interdiction contractuelle est une peine conventionnelle soumise à l'<ref-law>. Devant la Cour d'appel, sur la base de cette disposition, le demandeur a obtenu que l'indemnité soit réduite à deux mois de salaire seulement, au lieu de trois selon le contrat. En instance fédérale, il demande subsidiairement, s'il doit acquitter l'indemnité, que celle-ci soit réduite au montant symbolique d'un franc.
Aux termes de l'<ref-law>, 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).
Le demandeur fait état du désaccord qui existait entre les parties au sujet du décompte des jours de vacances et, sommairement, il revient sur les circonstances déjà prises en considération par la Cour d'appel. Celle-ci a comparé le montant de l'indemnité avec ce que la défenderesse aurait gagné si le demandeur s'était fait réengager par elle pour une durée supplémentaire de trois mois; après réduction, l'indemnité est inférieure à cette perte de gain. Il n'apparaît pas que la Cour ait mésusé de son pouvoir d'appréciation et rien n'impose une réduction plus importante de l'indemnité.
5. 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. Le demandeur acquittera un émolument judiciaire de 1'000 francs.
3. Le demandeur versera une indemnité de 2'000 fr. à la défenderesse, à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Cour d'appel de la juridiction des prud'hommes du canton de Genève.
Lausanne, le 6 juillet 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La présidente: Le greffier:
Klett Thélin