Faits: A. Dès la fin de l'été 2004, A._ a travaillé auprès des époux X._ en qualité d'employée de maison. Le 7 juillet 2006, elle leur a annoncé être enceinte. Suite à une chute au domicile de ses employeurs, elle a été en incapacité de travail du 8 au 30 août 2006. Elle n'a plus retravaillé pour les époux X._ depuis lors. A plusieurs reprises en septembre 2006, elle leur a offert ses services et requis le paiement de son salaire. B. Le 27 novembre 2006, l'employée a ouvert action contre ses employeurs, en paiement de la somme de 102'560 fr. 25 et en délivrance d'un certificat de travail. Par jugement du 9 janvier 2008, le Tribunal des prud'hommes du canton de Genève a condamné les employeurs à payer à l'employée la somme brute de 43'929 fr. 40 avec intérêts à 5 % l'an dès le 9 août 2006 et à établir un certificat de travail. Il a en revanche rejeté les conclusions de l'employée en paiement de 42'626 fr. à titre de salaire jusqu'à la fin de sa grossesse et pendant le délai de congé d'un mois; il a retenu que l'employée avait donné son congé en juillet 2006 pour le 31 août 2006, et en conséquence nié une résiliation en temps inopportun de la part des employeurs. L'employée a interjeté appel, concluant à l'annulation du jugement en tant qu'il concerne la fin des rapports de service, à ce qu'il soit constaté que son licenciement est intervenu en temps inopportun et à ce que les employeurs soient condamnés au versement de son salaire pendant toute la durée de la grossesse y compris pendant le délai post-natal, ainsi qu'à une indemnité pour licenciement en temps inopportun. Les employeurs ont conclu à l'irrecevabilité de l'appel faute de conclusions chiffrées et, par appel incident, au rejet de toutes les conclusions en paiement. Par jugement du 23 février 2009, la Cour d'appel de la juridiction des prud'hommes du canton de Genève a admis l'appel et rejeté l'appel incident. Elle a condamné les employeurs à payer à l'employée la somme nette de 42'626 fr. et la somme brute de 43'929 fr. 40, les deux avec intérêts à 5 % l'an dès le 9 août 2006. Elle a en outre invité la partie qui en a la charge à opérer les déductions légales et sociales usuelles, et condamné les employeurs à établir un certificat de travail. C. Les époux X._ (les recourants) ont formé un recours en matière civile au Tribunal fédéral. Ils concluaient à ce que l'appel cantonal de leur adverse partie soit déclaré irrecevable et à ce que celle-ci soit déboutée de toutes ses conclusions prises en appel, avec suite de dépens des instances cantonales et fédérale; ils précisaient attaquer le jugement d'appel uniquement sur la question de la fin des rapports de service, que la cour cantonale avait selon eux à tort qualifiée comme constituant un licenciement donné en temps inopportun; ils déclaraient par contre expressément renoncer à contester le montant de 43'929 fr. 40 alloué à titre d'heures supplémentaires, vacances non prises, etc. Ils demandaient également l'effet suspensif, qui a été accordé par ordonnance présidentielle du 12 mai 2009. A._ (l'intimée) a proposé principalement l'irrecevabilité, subsi-diairement le rejet du recours, sous suite de dépens.