Faits:
A. Dès le 1er août 2001, Y._ SA a engagé X._ en qualité de conseiller en personnel au sein de son agence de Genève. Le 1er février 2002, l'employé a été promu au rang de responsable d'agence. Le 13 février 2003, il a été inscrit comme directeur de la succursale genevoise, avec signature individuelle, pour les affaires liées à celle-ci; bénéficiant d'une grande confiance de la part de A._, administrateur et président, il s'est vu confier des responsabilités supplémentaires au fur et à mesure des relations de travail, si bien qu'il a finalement été chargé de la gestion de la succursale de Genève, mais également des agences de ... et .... En dernier lieu, le salaire mensuel brut de X._ s'élevait à 12'000 francs.
Le 5 avril 2007, X._ a demandé à rencontrer A._ pour faire le point de la situation; à la suite d'un entretien qui s'est déroulé début avril 2007, l'employeuse, soupçonnant des agissements "peu clairs" de la part de son employé, a confié à un expert financier la tâche de procéder à la vérification des comptes de sa succursale de Genève; l'audit a eu lieu des 17 et 18 avril 2007.
Le 19 avril 2007, X._ s'est trouvé en incapacité de travail à 100 % pour cause de maladie. Le même jour, B._, employée de Y._ SA à Genève en qualité de temporaire, s'est adressée par télécopie à A._ pour lui faire savoir qu'entrée en fonction en décembre 2005, elle s'était rapprochée très rapidement de X._; fragilisée à ce moment-là par une relation amoureuse qui l'avait beaucoup marquée, elle avait apprécié le comportement "très amical" de X._, qui s'intéressait à sa vie personnelle; le soir de la fête de fin d'année des temporaires, celui-ci lui avait proposé de la ramener à son domicile en voiture et ils avaient entretenu des relations sexuelles, de même qu'à une autre reprise dans les jours qui avaient suivi; pendant la période des fêtes de fin d'année, au cours de laquelle elle avait dû assurer la permanence, C._, client de Y._ SA, était passé plusieurs fois à la réception; X._ lui avait laissé entendre qu'elle intéressait ledit client, ce à quoi elle avait répondu que ce n'était pas son cas; le vendredi précédent Noël, tous trois étaient allés manger au restaurant durant la pause de midi; à leur retour à l'agence, X._ était allé travailler dans son bureau et elle à la réception; c'était alors que C._ lui avait demandé de lui céder sa place, afin de pouvoir travailler sur son ordinateur; quand elle s'était levée, C._ avait procédé à des attouchements auxquels elle avait "rétorqué en disant clairement non"; elle avait alors commencé à paniquer, car il devenait de plus en plus entreprenant, et avait appelé au secours X._, dont la porte du bureau était entrouverte, mais celui-ci n'était pas venu et avait simplement dit "faites comme si je n'étais pas là"; à ce moment-là, elle s'était vraiment sentie humiliée et seule au monde; C._ avait continué malgré ses cris, ses appels et ses refus; c'était alors qu'elle lui avait attrapé le poignet en le serrant fort et l'avait regardé droit dans les yeux en lui disant d'arrêter tout de suite, sinon cela allait mal se passer; là, l'intéressé avait repris ses esprits et s'était ensuite excusé, lui disant qu'il ne savait pas ce qui lui avait pris et que, de toute façon, elle était "bandante" (sic).
Par lettre du 20 avril 2007 reçue le 23 avril 2007, Y._ SA a résilié avec effet immédiat le contrat de travail la liant à X._; ce courrier indiquait notamment que l'audit avait révélé des irrégularités comptables qui lui étaient imputables; en particulier, il avait bénéficié de remboursements de frais sur la base de justificatifs irréguliers; en outre, il avait procédé à des sorties de caisse qui avaient servi à payer des factures qui n'étaient pas justifiées; finalement, l'une des employées qu'il avait sous sa responsabilité avait informé qu'il avait eu un comportement totalement inacceptable à son égard et qu'il avait laissé se créer une situation dangereuse pour elle; tous ces éléments faisaient que les rapports de confiance étaient définitivement rompus et qu'il était impossible pour l'employeuse de continuer à travailler avec lui.
B. Par demande du 24 mai 2007, X._ a assigné Y._ SA devant la Juridiction des prud'hommes du canton de Genève, en paiement de la somme de 65'180 fr. - ultérieurement augmentée de 24'000 fr. - avec intérêt à 5 % l'an dès le 23 avril 2007, correspondant en particulier à 27'000 fr. de salaire du 23 avril 2007 à la fin du délai de congé et à 24'000 fr. d'indemnité pour licenciement immédiat injustifié; l'employeuse a conclu au rejet et pris diverses conclusions reconventionnelles.
Par jugement du 26 mars 2008, le Tribunal des prud'hommes du canton de Genève a condamné d'une part Y._ SA à payer à X._ la somme de 8'000 fr. bruts avec intérêt à 5 % l'an dès le 23 avril 2007 à titre d'indemnité pour vacances non prises en nature, d'autre part celui-ci à verser à celle-là la somme de 30'000 fr. nets à titre de peine conventionnelle consécutive à une violation d'une clause de non-concurrence, ainsi qu'à lui restituer le téléphone et l'ordinateur portable lui appartenant.
Statuant sur appel de X._ et appel incident de Y._ SA par arrêt du 21 août 2009, la Cour d'appel de la juridiction des prud'hommes du canton de Genève a annulé le jugement de première instance (2) et, statuant à nouveau, en particulier condamné Y._ SA à payer à X._ la somme de 8'000 fr. bruts avec intérêt à 5 % l'an dès le 23 avril 2007 (3), condamné Y._ SA à restituer à X._ différents objets personnels (5), condamné X._ à payer à Y._ SA la somme de 50'000 fr. avec intérêt à 5 % l'an dès le 23 avril 2007 (6), condamné X._ à restituer à Y._ SA le téléphone et l'ordinateur portable appartenant à la société qu'il avait gardés par devers lui (7), statué sur les frais et dépens (8 à 13) et débouté les parties de toutes autres conclusions (14).
C. X._ (le recourant) interjette un recours en matière civile au Tribunal fédéral; il conclut, avec suite de dépens, principalement à l'annulation des chiffres 6 à 14 de l'arrêt du 21 août 2009, à la condamnation de Y._ SA à lui payer les sommes de 27'000 fr. bruts à titre de salaire pour la période résultant du délai de congé légal ainsi que de 24'000 fr. nets à titre d'indemnité pour licenciement avec effet immédiat injustifié et à la confirmation de la décision entreprise pour le surplus, subsidiairement au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Y._ SA (l'intimée) propose, sous suite de frais et dépens, le déboutement de son adverse partie de toutes ses conclusions et par conséquent la confirmation de l'arrêt du 21 août 2009.

Considérant en droit:
1. Interjeté par le recourant qui a partiellement succombé dans ses conclusions (<ref-law>) et dirigé contre une décision finale (<ref-law>) rendue en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>) dans une affaire dont la valeur litigieuse dépasse le seuil de 15'000 fr. applicable en matière de droit du travail (<ref-law>), le recours en matière civile présentement soumis à l'examen du Tribunal fédéral est en principe recevable, puisqu'il a été déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi.
2. Le recours en matière civile peut être formé pour violation du droit fédéral (<ref-law>), y compris le droit constitutionnel (<ref-ruling> consid. 1.2 p. 382). Saisi d'un tel recours, le Tribunal fédéral applique le droit d'office (<ref-law>) sur la base des faits établis par l'autorité précédente (<ref-law>), dont il ne peut s'écarter que s'ils l'ont été de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 8.1; <ref-ruling> consid. 1.5 p. 130) - ou en violation du droit au sens de l'<ref-law> (<ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>). La partie recourante qui entend contester les constatations de l'autorité précédente doit expliquer de manière circonstanciée en quoi les conditions de l'exception prévue par l'<ref-law> sont réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (<ref-ruling> consid. 2.4 p. 466 s.). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
3. A titre liminaire, il y a lieu de relever que, dans son écriture au Tribunal fédéral, le recourant conclut à l'annulation des chiffres 6 et 7 du dispositif de l'arrêt attaqué; à défaut de toute argumentation à ce sujet, il n'y a toutefois pas lieu d'entrer en matière. Seule demeure donc litigieuse la question de l'existence de justes motifs de licenciement immédiat.
4. En l'occurrence, la cour cantonale a considéré qu'il était résulté du contrôle interne de la comptabilité de l'agence genevoise que le recourant avait fait établir deux "fausses factures" par une société tierce, l'une de complaisance destinée à rémunérer un intermédiaire et l'autre dans le but de payer un dénommé D._, dont le recourant avait expressément admis la fausseté; dès lors que l'établissement de ce document ne correspondait pas à la réalité, il importait peu qu'elle ait ou non servi à la rétribution d'un travail accompli pour l'intimée par D._; au demeurant, les explications fournies par le recourant à cet égard n'étaient pas claires et tout sauf convaincantes.
Par ailleurs, il résultait des déclarations du témoin E._ - que l'on ne pouvait soupçonner de complaisance à l'égard de l'intimée au vu de sa déposition, plutôt critique vis-à-vis de celle-ci - qu'à la fin de l'année 2005, B._ lui avait téléphoné à son domicile pour lui faire part des approches à caractère sexuel que C._ avaient entreprises à son endroit, l'intéressée n'étant "pas bien du tout" lors de ce téléphone, quand bien même elle n'était pas en pleurs; le témoin avait précisé qu'il n'avait pas eu l'impression que B._ avait inventé cette histoire. Dans ces conditions, le témoignage de C._ - qu'il convenait d'apprécier avec toute la circonspection qui s'imposait, l'intéressé étant concerné au premier chef par la question - n'était pas de nature à remettre en cause la véracité des déclarations de B._ au sujet de l'épisode de Noël 2005; certes, l'on pouvait s'interroger au sujet de sa conduite ultérieure à l'égard de C._, voire du recourant, l'intéressée n'ayant pris aucune mesure particulière pour éviter d'être en contact professionnellement avec le premier et ayant continué à entretenir des rapports professionnels "normaux" avec le second; toutefois, ce comportement de B._ pouvait essentiellement s'expliquer par le fait qu'à l'époque, elle était employée temporairement par l'intimée et ne voulait pas perdre son emploi, notamment en étalant au grand jour les événements mettant en particulier en cause son supérieur hiérarchique; au dire de B._, ce dernier ne s'était du reste pas fait faute de lui rappeler ultérieurement, lorsqu'elle lui avait reparlé de cet épisode, que leur sort professionnel était lié et que s'il était licencié, elle le serait également; en outre, il ressortait de la procédure que cette jeune femme, âgée de vingt-quatre ans au moment des faits, était assez instable et fragile sentimentalement, voire provocante avec les hommes, de sorte que ces éléments avaient certainement constitué pour elle un obstacle l'empêchant de se plaindre tout de suite auprès de sa hiérarchie ou de ses collègues de travail des événements qui s'étaient passés à fin 2005. Le fait que, selon le témoin E._, la directrice de l'agence genevoise de l'intimée ait cherché, avec ses collaborateurs, des motifs de se séparer rapidement du recourant, n'était pas non plus de nature à remettre en cause la véracité des déclarations de B._; en effet, il résultait également du témoignage de E._ que c'était lui qui avait été parler de l'épisode et qu'au début, B._ n'était pas "très d'accord de mettre par écrit cette histoire", comme sa directrice le lui avait demandé, de sorte que c'était lui qui l'avait encouragée à le faire; quelle qu'ait été l'attitude de la directrice, lors des enquêtes de première instance, en particulier à l'égard du témoin E._, les déclarations de ce dernier - qui n'était plus employé de l'intimée, ce qui expliquait sans doute sa plus grande liberté de parole qu'en première instance - devant la Cour d'appel apparaissaient crédibles, de sorte que l'on pouvait pratiquement exclure se trouver en présence d'une "odieuse mise en scène préparée par l'intimée", comme l'affirmait péremptoirement le recourant, consistant à pousser B._ à inventer de toute pièce, dans le but de le faire licencier, les faits qu'elle avait dénoncés; quoi qu'il en était à cet égard, il découlait de l'ensemble de ce qui précédait qu'il devait être retenu que C._ s'était autorisé, à fin 2005, des primautés de nature sexuelle à l'égard de B._ et que le recourant, alors qu'il n'ignorait pas ce qui se passait, n'avait rien fait pour l'en empêcher, en dépit de l'appel à l'aide que l'intéressée lui avait adressé.
Le comportement du recourant, que ce soit à la fin de l'année 2005 envers une subordonnée ou en établissant de fausses factures - quelles qu'en soient les raisons -, constituait, de la part d'un cadre occupant la position du recourant, des manquements particulièrement graves à ses obligations contractuelles de fidélité et de diligence à l'égard de son employeur. On pouvait ainsi admettre qu'en ayant connaissance des agissements du recourant le 19 avril 2007, l'intimée ait estimé que ceux-ci étaient si graves qu'ils entraînaient la perte immédiate du rapport de confiance avec le recourant et n'autorisaient pas la résiliation de son contrat de travail en respectant le délai de deux mois prévu contractuellement.
5. Invoquant l'art. 9 Cst., le recourant reproche aux juges cantonaux d'avoir fait preuve d'arbitraire dans l'appréciation des preuves et l'établissement des faits "en ne prenant pas en compte divers éléments de faits ou moyens de preuve en ce qui concerne l'épisode de prétendu harcèlement relaté par Madame B._, et en ne considérant que le témoignage de cette dernière, par ailleurs contesté tant par le recourant que par les autres éléments de la procédure".
5.1 Selon la jurisprudence, une décision est arbitraire, au sens de l'art. 9 Cst., lorsqu'elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté, ou heurte de manière choquante le sentiment de la justice et de l'équité; il ne suffit pas qu'une autre solution paraisse concevable, voire préférable; pour que cette décision soit annulée, encore faut-il qu'elle se révèle arbitraire, non seulement dans ses motifs, mais aussi dans son résultat, ce qu'il appartient à la partie recourante de démontrer en vertu de l'<ref-law> (<ref-ruling> consid. 3.1 p. 265 s.).
Dans la mesure où l'arbitraire est invoqué en relation avec l'établissement des faits, il convient de rappeler que le juge dispose d'un large pouvoir lorsqu'il apprécie les preuves (<ref-ruling> consid. 4b). La partie recourante doit ainsi expliquer dans quelle mesure le juge a abusé de son pouvoir d'appréciation et, plus particulièrement, montrer qu'il a omis, sans aucune raison sérieuse, de prendre en compte un élément de preuve propre à modifier la décision attaquée, qu'il s'est manifestement trompé sur son sens et sa portée ou encore que, en se fondant sur les éléments recueillis, il en a tiré des constatations insoutenables (<ref-ruling> consid. 4.3; <ref-ruling> consid. 2.1)
5.2 En l'occurrence, le recourant estime premièrement que ni les déclarations de C._, ni celles de E._ n'attesteraient la véracité des propos tenus par B._, contrairement à ce que la cour cantonale aurait retenu de manière insoutenable. A ce propos, il se limite cependant à mentionner quelques extraits des auditions des témoins en question, ce qui n'est pas de nature à établir en quoi les juges cantonaux seraient parvenus à une conclusion arbitraire, à l'issue d'un raisonnement circonstancié exposant notamment les raisons pour lesquelles les déclarations de E._ étaient dignes de foi, au contraire de celles de C._ qui devaient être appréciées avec retenue.
Le recourant soutient ensuite que les juges cantonaux auraient commis arbitraire en considérant que le comportement provocant de B._ avec les hommes aurait été l'un des facteurs l'ayant empêchée de se plaindre tout de suite après les faits auprès de sa hiérarchie. La pertinence de cet élément importe en réalité peu, dès lors qu'il n'est pas à lui seul déterminant; c'est en effet à l'issue d'une appréciation globale de la situation que la cour cantonale a considéré que l'attitude de B._ après l'épisode litigieux n'était pas de nature à remettre en cause la réalité du récit que celle-ci en avait fait; à cet égard, les juges cantonaux ont également tenu compte de la situation de l'intéressée, dont la qualité d'employée temporaire rendait délicat de dénoncer son supérieur hiérarchique, par crainte d'un licenciement; à supposer fondé, question qui peut être laissée ouverte, le grief du recourant serait ainsi de toute façon dénué d'incidence sur le sort du litige.
Le recourant est enfin d'avis que la cour cantonale aurait "estimé de manière surprenante" que le fait que la directrice genevoise de l'intimée ait cherché des motifs de se séparer de lui n'était pas de nature à remettre en cause les déclarations de B._; à cet égard, il ne fait cependant que mettre en exergue un certain nombre d'éléments, selon lui "raisonnablement admis, par la procédure", qu'il estime utiles à sa thèse, sans à proprement parler critiquer les raisons pour lesquelles les juges cantonaux ont considéré que la circonstance en question n'était pas susceptible de compromettre la véracité des déclarations de B._; purement appellatoire, ce mode de procéder n'est pas de nature à démontrer l'arbitraire; au demeurant, la manière dont les éléments litigieux, invoqués au titre de motifs de licenciement immédiat, ont été découverts ne change rien au fait que leur réalité a bel et bien été établie.
5.3 Dans le même contexte, le recourant, se prévalant de l'art. 29 al. 2 Cst., estime que la cour cantonale aurait violé son droit d'être entendu en refusant d'entendre à nouveau B._ en appel; à ce propos, il mentionne un passage du témoignage de E._ dont il résulterait que la directrice genevoise de l'intimée aurait félicité B._ pour son témoignage et que celle-ci aurait rigolé à sa sortie du tribunal.
Sur ce point, la cour cantonale a considéré qu'il n'y avait pas à procéder à une nouvelle audition de B._, dès lors que la véracité de son témoignage avait été établie par d'autres éléments du dossier, spécifiquement les déclarations du témoin E._; elle a relevé qu'au demeurant, il était également significatif qu'à l'issue de l'audition de B._, le recourant n'ait pas contesté ses déclarations.
Dans la mesure où les juges cantonaux ont, comme précédemment exposé, forgé leur conviction à l'issue d'une appréciation des faits exempte d'arbitraire, en s'appuyant en particulier sur le témoignage de E._, ils étaient fondés à se passer d'entendre une nouvelle fois B._, dont l'intimée souligne d'ailleurs que le recourant ne l'aurait pas citée comme témoin dans son mémoire d'appel et de réponse sur appel incident, question qui peut toutefois être laissée indécise. En définitive, le grief, qui se confond dans le cas particulier avec celui d'arbitraire dans l'appréciation des preuves et l'établissement des faits, doit donc être rejeté.
6. Le recourant soutient que la cour cantonale aurait violé l'<ref-law> en retenant à tort l'existence de justes motifs; les juges cantonaux auraient erré en considérant que les faits qui lui étaient reprochés étaient à ce point graves qu'ils ne permettaient pas la résiliation du contrat de travail en respectant le délai de congé de deux mois prévu contractuellement.
6.1 Aux termes de l'art. 337 al. 1 1e phrase CO, l'employeur et le travailleur peuvent résilier immédiatement le contrat en tout temps pour de justes motifs. Doivent notamment être considérées comme tels toutes les circonstances qui, selon les règles de la bonne foi, ne permettent pas d'exiger de celui qui a donné le congé la continuation des rapports de travail (<ref-law>).
Mesure exceptionnelle, la résiliation immédiate pour justes motifs doit être admise de manière restrictive. D'après la jurisprudence, les faits invoqués à l'appui d'un renvoi immédiat doivent avoir entraîné la perte du rapport de confiance qui constitue le fondement du contrat de travail. Seul un manquement particulièrement grave du travailleur justifie son licenciement immédiat; si le manquement est moins grave, il ne peut entraîner une résiliation immédiate que s'il a été répété malgré un avertissement (<ref-ruling> consid. 4.1, 213 consid. 3.1 p. 220 s.). Par manquement du travailleur, on entend en règle générale la violation d'une obligation découlant du contrat de travail (<ref-ruling> consid. 4.1 p. 31; <ref-ruling> consid. 4a p. 354), comme par exemple le devoir de fidélité (ATF <ref-ruling> consid. 4a p. 354; <ref-ruling> consid. 4d). A raison de ce dernier devoir, le travailleur est tenu de sauvegarder les intérêts légitimes de son employeur (<ref-law>) et, par conséquent, de s'abstenir de tout ce qui peut lui nuire (<ref-ruling> consid. 3a p. 27; <ref-ruling> consid. 3a p. 561). Le comportement des cadres doit être apprécié avec une rigueur accrue en raison du crédit particulier et de la responsabilité que leur confère leur fonction dans l'entreprise (<ref-ruling> consid. 4.1 p. 31; <ref-ruling> consid. 2c p. 89).
Le juge apprécie librement s'il existe de justes motifs (<ref-law>). Il applique les règles du droit et de l'équité (<ref-law>). A cet effet, il prendra en considération tous les éléments du cas particulier, notamment la position et la responsabilité du travailleur, le type et la durée des rapports contractuels, ainsi que la nature et l'importance des manquements (<ref-ruling> consid. 4.1 p. 32; <ref-ruling> consid. 4a p. 354). Le Tribunal fédéral revoit avec réserve la décision d'équité prise en dernière instance cantonale. Il intervient lorsque celle-ci s'écarte sans raison des règles établies par la doctrine et la jurisprudence en matière de libre appréciation, ou lorsqu'elle s'appuie sur des faits qui, dans le cas particulier, ne devaient jouer aucun rôle, ou à l'inverse, lorsqu'elle n'a pas tenu compte d'éléments qui auraient absolument dû être pris en considération; il sanctionnera en outre les décisions rendues en vertu d'un pouvoir d'appréciation lorsqu'elles aboutissent à un résultat manifestement injuste ou à une iniquité choquante (<ref-ruling> consid. 4.1 p. 32, 213 consid. 3.1 p. 220).
6.2 Concernant le premier motif de licenciement, le recourant expose en bref que la facture établie par la société tierce n'avait jamais eu pour objectif son enrichissement mais la rémunération d'un tiers pour du travail effectué pour l'intimée, qu'il n'avait jamais bénéficié d'une formation dans le domaine de la comptabilité, que l'intimée n'avait jamais établi la moindre directive interne en rapport avec les pièces comptables ou les dépenses qui étaient occasionnées par son personnel, enfin que le montant de la facture restait des plus modestes; son manquement, mineur et non répété, ne serait ainsi pas assez grave pour justifier le licenciement immédiat.
Quant au second motif de résiliation, le recourant, qui souligne que l'intimée ne l'a pas entendu préalablement à son licenciement sur les faits décrits par B._, plaide que l'acte de harcèlement était le fait d'un tiers, que l'épisode n'avait duré que quelques secondes et que l'intéressée avait réussi à y mettre un terme toute seule; il estime que dans ces circonstances, sa passivité n'était pas assez grave pour justifier un licenciement abrupt.
Il est constant que l'employeur doit protéger la personnalité de ses employés, en particulier veiller à ce que ceux-ci ne soient pas harcelés sexuellement (<ref-law>); cette obligation vaut pour les cadres de l'entreprise, auxiliaires de l'employeur. Or, il apparaît que le recourant y a en l'espèce gravement contrevenu; il a en effet été constaté - sans arbitraire - qu'il n'avait pas réagi à l'appel à l'aide de sa collaboratrice B._ qui était victime d'attouchements de la part du client C._, mais s'était au contraire fendu d'une remarque selon laquelle ils devaient "faire comme s'il n'était pas là", abandonnant ainsi totalement l'intéressée; un tel comportement est inadmissible et constituait à lui seul un motif suffisant pour permettre à l'intimée de procéder à un licenciement immédiat sitôt après avoir pris connaissance - certes plusieurs mois plus tard - de l'événement; la cour cantonale n'a ainsi pas violé le droit fédéral et le grief doit être écarté sans qu'il soit nécessaire d'examiner l'argumentation du recourant relative au premier motif de résiliation.
7. Il résulte des considérants qui précèdent que le recours doit être rejeté dans la mesure de sa recevabilité.
8. Comme la valeur litigieuse, calculée selon les prétentions à l'ouverture de l'action (<ref-ruling> consid. 5b p. 41), dépasse le seuil de 30'000 fr., le montant de l'émolument judiciaire est fixé selon le tarif ordinaire (<ref-law>) et non réduit (art. 65 al. 4 let. c LTF). Compte tenu de l'issue du litige, les frais judiciaires et dépens de l'intimée doivent être mis à la charge du recourant, qui succombe (art. 66 al. 1 ainsi qu'art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3. Une indemnité de 3'500 fr., à payer à l'intimée à titre de dépens, est mise à la charge du recourant.
4. Le présent arrêt est communiqué aux mandataires des parties et à la Cour d'appel de la juridiction des prud'hommes du canton de Genève.
Lausanne, le 11 décembre 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Klett Cornaz