Faits: A. Par contrat de bail à loyer du 17 mai 1989, la Caisse Z._ (ci-après: Z._) a remis à bail à T._ des locaux commerciaux, situés au 1er étage d'un immeuble, à Genève. Le bail, conclu pour une durée initiale de cinq ans et quinze jours (soit du 15 mai 1989 au 31 mai 1994), était renouvelable tacitement de cinq ans en cinq ans, sauf congé donné au moins six mois à l'avance. Le loyer, indexé à l'indice suisse des prix à la consommation, s'élevait à 28'176 fr. par an et la garantie de loyer a été fixée à 7'044 fr., soit trois mois de loyer. Le 12 juin 1989, Y._ SA s'est substituée à T._ en tant que locataire, puis celui-ci est redevenu locataire des locaux le 9 août 1989, conjointement et solidairement avec Y._ SA. Le 8 février 1999, X._, administratrice de cette dernière société, s'est substituée à T._ et est devenue locataire conjointe et solidaire des locaux avec Y._ SA. Malgré les changements successifs de locataires, les autres clauses du bail sont restées les mêmes. Par avenant du 4 juillet 2002, l'échéance du bail a été reportée du 31 mai 2004 au 31 mai 2007. Par avis de majoration du 22 avril 2005, le loyer annuel a été fixé en dernier lieu à 37'560 fr., charges non comprises. Le 30 novembre 2005, X._ a informé Z._ de son intention de résilier le bail par anticipation pour le 31 décembre 2005. Le 9 décembre 2005, dans un courrier adressé à Y._ SA et à X._, la régie B._ SA (ci-après: la régie), mandataire de Z._, a attiré l'attention de la dernière locataire qu'à défaut de trouver un locataire de remplacement au sens de l'art. 264 CO, elle demeurait tenue des obligations découlant du contrat jusqu'à sa prochaine échéance, soit le 31 mai 2007. Sur proposition de X._, A._ SA (ci-après: A._), société avec siège à Genève, récemment inscrite au registre du commerce, a indiqué à la régie qu'elle se portait candidate à la location des locaux. Elle a d'emblée précisé les conditions de son "inscription" comme suit: "Loyer mensuel: 3'000.--/mois Charges mensuels: 230.--/mois Durée du bail: 5 ans (clause de résiliation anticipée sans pénalité après 3 ans) Garantie de loyer: 6 mois (garantie bancaire ou dépôt) Date d'entrée: souhaitée par le bailleur 15.09.2006 Idéale (...) entre le 01.10.2006 et le 15.10.2006" Par courriel du 31 août 2006, la régie a informé l'administrateur de A._ que la candidature de la société était acceptée aux conditions suivantes: "Loyer: identique à celui de l'ancien locataire, soit CHF 3'130.00/mois. Charges: CHF 230.00/mois. Durée du bail: 5 ans indexé avec clause de résiliation anticipée dès la troisième année. Garantie: 6 mois si une personne physique suisse solvable est cotitulaire du bail, 1 année si la société est seule titulaire du bail. Date d'entrée: à définir." Par courriel du 6 septembre 2006, l'administrateur de A._ confirmait à la régie les "points convenus entre les parties" lors d'une réunion s'étant tenue le même jour, de la façon suivante: "Loyer mensuel: CHF 3'130.00/mois. Charges: CHF 230.00/mois. Date d'entrée: le lundi 18.09.2006 Caution de la Maison mère C._ à Paris à concurrence de 6 mois de loyer Dépôt de garantie de A._ SA, Genève à concurrence de 6 mois de loyer" Par courrier de leur mandataire du 26 septembre 2006, Y._ SA et X._ ont indiqué à la régie qu'au vu de l'accord qui semblait avoir été conclu entre la bailleresse et A._, elles considéraient leur bail valablement résilié pour le 30 septembre 2006. Le 29 septembre 2006, la régie a répondu qu'elle ne pouvait accepter la proposition formulée par A._ le 6 septembre 2006, en raison de la complication des démarches qui devraient, le cas échéant, être entreprises contre sa maison mère C._ à Paris, dont la solvabilité était difficilement appréciable, en cas de défaut de paiement de loyer. X._ ayant restitué les clés des locaux le 9 octobre 2006, la régie a indiqué, sur le reçu, que les clés étaient acceptées "sans libération des locataires par anticipation" et que le congé était admis pour le 31 mai 2007. B. Après un nouvel échange de courrier entre la régie et le mandataire de X._, Z._ a fait notifier, le 19 décembre 2006, un commandement de payer à cette dernière portant sur la somme de 10'800 fr. plus intérêts (au titre d'arriérés de loyers et charges du 1er octobre au 31 décembre 2006). La locataire y a fait opposition. Le 22 mars 2007, le Juge de paix des districts de Nyon et Rolle a rejeté la requête de mainlevée déposée par Z._. Z._ a fait notifier, le 12 janvier 2007, un commandement de payer à Y._ SA. Le Tribunal de première instance de Genève a prononcé la mainlevée provisoire de l'opposition formée par la locataire. Y._ SA a déposé une demande en libération de dette et action en constatation négative de droit le 28 juin 2007. Suite à la non- conciliation devant la commission compétente, la demande a été portée devant le Tribunal des baux et loyers le 18 octobre 2007. Y._ SA a conclu principalement à ce qu'elle soit libérée, dès le 1er octobre 2006, de toute obligation en rapport avec son contrat de bail. Z._ a dirigé une action en paiement contre X._ qui a été portée, la conciliation ayant échoué, devant le Tribunal des baux et loyers le 19 novembre 2007. Elle a conclu à ce que la locataire soit condamnée à lui payer la somme de 26'880 fr. plus intérêts, correspondants aux loyers et charges dus pour la période du 1er octobre 2006 au 31 mai 2007. Les parties ont requis la jonction des causes en une seule procédure. Lors de l'instruction, deux témoins - une courtière auprès de la régie et le gérant de l'immeuble en cause - ont été entendus. En substance, ils ont rapporté que dès lors que A._ était une société nouvellement créée et qu'il s'est avéré difficile d'apprécier la solvabilité de sa société mère sise en France, la propriétaire des locaux commerciaux avait considéré que les garanties proposées par A._ n'étaient pas suffisantes. Ayant préalablement joint les causes, le Tribunal des baux et loyers a, par jugement du 17 décembre 2008, estimé que les locataires sortantes avaient suffisamment démontré que leur candidate était solvable et objectivement acceptable. Ayant par ailleurs retenu que A._ avait accepté de signer un bail dont les conditions étaient globalement identiques à celles du bail d'origine, il a libéré Y._ SA de toute obligation en rapport avec le contrat de bail conclu avec Z._ et débouté cette dernière de toute conclusion prise à l'encontre de X._. Saisi d'un appel de la bailleresse, 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 7 septembre 2009, annulé le jugement attaqué et, statuant à nouveau, condamné X._ à verser à Z._ le montant de 20'160 fr., plus intérêts, et prononcé à due concurrence la mainlevée de l'opposition formée par Y._ SA. C. Les locataires exercent un recours en matière civile au Tribunal fédéral contre l'arrêt du 7 septembre 2009. Reprochant à la cour cantonale d'avoir violé l'art. 264 CO en n'ayant pas considéré comme acceptable la locataire de remplacement qu'elles avaient proposée à la bailleresse, les recourantes concluent à l'annulation de l'arrêt attaqué et, en substance, à la confirmation du jugement du Tribunal des baux et loyers du 17 décembre 2008. L'intimée conclut au rejet du recours formé par Y._ SA et X._, sous suite de dépens.