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. 