Faits: A. Dame A._ et A._ sont copropriétaires de l'appartement 6.03 de 4,5 pièces au 4ème étage de l'immeuble situé avenue Ernest-Pictet au Petit-Saconnex. Selon un bail conclu le 26 août 2009, les époux A._ ont mis ce bien en location du 1er septembre 2009 au 31 août 2012 pour un loyer annuel sans les charges de 30'000 fr. Devant partir à l'étranger, la locataire a toutefois résilié ce bail pour le 30 avril 2011. Selon une requête enregistrée le 6 mai 2011 par le département cantonal des constructions et des technologies de l'information, devenu le département de l'urbanisme (ci-après : le département), les époux A._ ont sollicité l'autorisation d'aliéner à B._ l'appartement précité, en indiquant pour motif « désendettement ». Par arrêté du 23 mai 2011, le département a autorisé la vente en question pour un prix total fixé à 850'000 fr. B. L'Association genevoise de défense des locataires (ci-après : l'ASLOCA) a recouru contre cette décision auprès du Tribunal administratif de première instance (ci-après : le TAPI). Après avoir entendu les parties en audience de comparution personnelle, le TAPI a rejeté le recours le 29 septembre 2011 et confirmé l'autorisation de vente délivrée par le département. Par arrêt du 20 novembre 2012, la Chambre administrative de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a admis le recours de l'ASLOCA et annulé le jugement du TAPI du 29 septembre 2011 ainsi que l'autorisation du 23 mai 2011. Elle a considéré en substance que, au vu de la pénurie sévère de logements locatifs dans le canton de Genève, l'intérêt public au maintien du parc locatif était prépondérant face aux intérêts privés du vendeur et de l'acquéreur. C. Agissant par la voie du recours en matière de droit public, Dame A._ et A._ demandent au Tribunal fédéral d'annuler l'arrêt de la Cour de justice du 20 novembre 2012, de dire que le recours de l'ASLOCA devant le TAPI était infondé et de rétablir l'autorisation litigieuse. Les recourants se plaignent pour l'essentiel d'une constatation inexacte et arbitraire des faits, d'une application arbitraire du droit cantonal ainsi que d'une violation du principe de la proportionnalité et de la garantie de la propriété. La Cour de justice s'en rapporte à justice quant à la recevabilité du recours et persiste dans les considérants et le dispositif de son arrêt. Le département s'en rapporte à justice quant au fond du litige. L'ASLOCA conclut à l'annulation de l'arrêt du TAPI et de l'autorisation d'aliéner et demande au Tribunal fédéral d'"ordonner [au] Conseil d'Etat de supprimer les «partages-attribution» ainsi que les «cessions-transferts» et les «cessions-attributions» et d'ordonner l'aliénation de l'application de toute les autorisations d'appartements de l'article 39 LDTR". Les recourants ont répliqué et maintenu leurs conclusions.