Faits: A. Depuis le 8 mars 2004, suite à un transfert de bail, H.X._ et F.X._ louent des locaux commerciaux à la Ville de Genève. Le bail porte sur un local d'environ 73 m2 au rez-de-chaussée et un autre d'environ 35 m2 au sous-sol d'un immeuble situé à Genève. Le loyer a été fixé à 19'224 fr. par année, charges non comprises. H.X._ et F.X._ sont propriétaires du fonds de commerce du café-restaurant "...", exploité dans les locaux commerciaux. Par un contrat conclu le 23 mars 2006, ils ont remis en gérance l'établissement "..." à Y._ (ci-après: la gérante) à compter du 1er mai 2006. La durée de la gérance a été fixée à l'art. 2 du contrat: "[Elle] est fixée pour une durée d'une année commençant le 1er mai 2006 et terminant le 30 avril 2007. Sauf avis contraire signifié à l'autre partie au plus tard 6 mois avant l'échéance, par lettre recommandée, le contrat sera reconduit d'année en année aux mêmes clauses et conditions ce, jusqu'à un total de 5 années". Selon l'art. 3 de la convention, la gérante s'est engagée à payer à H.X._ et F.X._, par mois d'avance, une indemnité mensuelle de 4'175 fr. (montant comprenant le loyer avec charges, la gérance et le garage). Enfin, l'art. 4 du contrat prévoit ce qui suit: "(...) pour l'obtention de l'exploitation du fonds de commerce un montant de 101'000 fr. est versé par le gérant au cédant, à la remise des clés. La différence pour avoir accès au bail est de 129'999 fr. Le gérant pourra en tout temps verser des acomptes" (al. 1). Le paiement du loyer-gérance se fera au plus tard le 5 du mois en cours. En cas de retard dans le paiement d'une quelconque indemnité mensuelle, le cédant pourra fixer au gérant un délai de 60 jours et lui signifiera qu'à défaut de paiement dans ce délai, il sera en droit de résilier la présente convention et le montant susmentionné de 101'000 fr. et les éventuels acomptes resteront en mains du cédant pour dédommagement" (al. 2). Par courrier du 30 novembre 2006, le mandataire de l'époque de la gérante a indiqué à H.X._ et F.X._ que sa cliente souhaitait acquérir la totalité du fonds de commerce et qu'elle avait versé, le 5 mai 2006, la somme de 179'900 fr.; la gérante sollicitait le transfert de bail en sa faveur. Le 6 décembre 2006, la fiduciaire de H.X._ et F.X._ a répondu au mandataire de la gérante que celle-ci n'avait rien versé et qu'elle devait toujours à H.X._ et F.X._ un montant de 18'262 fr. sur la base d'une reconnaissance de dette du 22 juin 2006. Dès le mois de mars 2007, la gérante a cessé le paiement de l'indemnité mensuelle prévue par le contrat. Par pli recommandé du 4 mai 2007, le conseil de H.X._ et F.X._ a mis en demeure la gérante de verser à ses clients, avant le 15 juillet 2007, la somme de 16'700 fr., à titre d'indemnités des mois de juin et de mars à mai 2007. Le courrier précisait: "Si vous ne vous conformez pas à cette injonction, Monsieur H.X._ et Madame F.X._ feront application de l'alinéa 2 de l'article 4 du contrat de bail". Par avis officiel du 16 juillet 2007, H.X._ et F.X._ ont résilié le contrat les liant à la gérante pour le 31 août 2007, en raison du non-paiement de l'indemnité mensuelle. Le 20 juin 2007, la gérante a versé 1'200 fr. à H.X._ et F.X._, et le même montant le 6 juillet 2007. Elle a également versé 14'400 fr. le 23 juillet 2007. B. La gérante a contesté le congé donné le 16 juillet 2007. La tentative de conciliation devant la Commission de conciliation en matière de baux et loyers ayant échoué, elle a introduit, le 12 décembre 2007, une requête en contestation du congé auprès du Tribunal des baux et loyers du canton de Genève. De leur côté, H.X._ et F.X._ ont sollicité l'évacuation de la gérante des locaux non libérés par elle à l'issue de la résiliation de bail. La tentative de conciliation s'étant soldée par un échec, ils ont saisi, le 5 mars 2008, le Tribunal des baux et loyers du canton de Genève de leur requête. Ayant ordonné la jonction des causes, le Tribunal des baux et loyers a, par jugement du 18 février 2009, constaté la validité du congé, condamné la gérante à évacuer immédiatement les locaux commerciaux, mis à sa charge les débours et débouté les parties de toutes autres conclusions. En substance, le Tribunal des baux et loyers a retenu que toutes les conditions légales relatives à la mise en demeure, à la résiliation du bail et à la demande d'évacuation étaient réunies. Il est arrivé à la conclusion qu'aucun des témoins n'avait été en mesure de confirmer que la gérante avait remis à H.X._ la somme de 180'000 fr. et qu'il était douteux qu'elle lui ait remis un tel montant sans lui demander de quittance. Saisie d'un appel de la gérante, la Chambre d'appel en matière de baux et loyers de la Cour de justice du canton de Genève a, par arrêt du 5 octobre 2009, annulé le jugement entrepris, constaté l'inefficacité de la résiliation adressée par H.X._ et F.X._ à Y._, condamné les premiers au paiement d'un émolument en faveur de l'Etat et débouté les parties de toutes autres conclusions. Sur la question de l'éventuelle remise d'un montant de 180'000 fr., la cour cantonale, considérant qu'il ne se justifiait pas d'ordonner la réouverture des enquêtes, a débouté l'appelante de ses conclusions sur ce point. S'agissant de la validité de la résiliation du bail à ferme liant les parties, elle a donné raison à l'appelante, considérant que si la sommation avait été valablement expédiée, elle ne contenait toutefois aucune menace de résiliation de bail et ne respectait donc pas l'exigence de l'art. 282 CO. C. H.X._ et F.X._ exercent un recours en matière civile contre l'arrêt cantonal du 5 octobre 2009. Ils concluent à l'annulation de l'arrêt entrepris et à la confirmation du jugement de première instance, à tout le moins au renvoi de la cause à la Cour de justice, sous suite de dépens. Subsidiairement, les recourants concluent à ce que Y._ soit déboutée de toutes autres ou contraires conclusions. L'intimée conclut à l'irrecevabilité du recours et, sur le fond, à son rejet et à la confirmation de l'arrêt de la Cour de justice, sous suite de dépens.