Faits: A. La SI A._, alors propriétaire, a remis à bail à H.X._, à compter du 1er juin 1977, un appartement de trois pièces ainsi qu'une grande chambrette dans un immeuble sis à Genève, Le loyer, sans les charges, était fixé en dernier lieu à 750 fr. par mois. Au mois de septembre 2004, Y._ a acquis l'immeuble, devenant la bailleresse. Par deux avis officiels du 3 juin 2005, adressés l'un à H.X._ et l'autre à son épouse F.X._, la bailleresse a résilié le contrat pour le 31 octobre 2005, affirmant qu'elle avait besoin des locaux loués pour son frère. B. H.X._ et F.X._ ont saisi la Commission de conciliation en matière de baux et loyers du canton de Genève, concluant principalement à l'annulation du congé et subsidiairement à une prolongation du bail. Ils soutiennent en substance que le besoin de la bailleresse n'est pas établi, qu'il n'est qu'un prétexte et qu'elle a eu d'autres occasions de loger ses proches. Par décision du 13 décembre 2005, la Commission de conciliation a admis la validité du congé, mais a accordé une première prolongation du bail de deux ans. La bailleresse a saisi le juge par demande du 3 janvier 2006, contestant la prolongation de bail accordée. H.X._ et F.X._, dans leur réponse, ont conclu principalement à l'annulation du congé et, subsidiairement, à sa prolongation pour la durée maximale. Par jugement du 11 octobre 2007, le Tribunal des baux et loyers du canton de Genève a déclaré le congé valable et accordé aux locataires une unique prolongation du bail de trois ans, soit au 31 octobre 2008. H.X._ et F.X._ ont appelé de ce jugement; ils ont conclu principalement à l'annulation du congé et subsidiairement à une prolongation du bail pour la durée maximale. La bailleresse a conclu à la confirmation du jugement attaqué. Par arrêt du 6 octobre 2008, la Chambre d'appel en matière de baux et loyers du canton de Genève a annulé le jugement entrepris et accordé une prolongation de bail de quatre ans. La cour cantonale a cependant considéré qu'il n'y avait pas lieu d'entrer en matière sur la question de la validité du congé, parce que H.X._ et F.X._ n'avaient pas saisi le juge dans les trente jours après la décision de la Commission de conciliation écartant leurs conclusions en annulation de la résiliation. C. H.X._ et F.X._ exercent un recours en matière civile au Tribunal fédéral. Ils concluent à l'annulation de l'arrêt attaqué et, principalement, à l'annulation du congé, subsidiairement au renvoi de la cause à la cour cantonale pour qu'elle annule le congé; plus subsidiairement, les recourants requièrent que la cause soit retournée à l'autorité cantonale pour compléter l'instruction. L'intimée propose le rejet du recours.