Faits: A. A._ était administrateur et actionnaire unique de la société SI Z._, propriétaire de l'art. ****, feuillet ** de la commune de C._, d'une surface de ***** m2 située en zone agricole, comportant une maison d'habitation, des serres, un hangar et un jardin. Il a exploité ce fonds agricole pendant plusieurs années. B._ est locataire du jardin, du hangar et de la maison, qu'elle habite avec A._ et leur enfant commun. Le 11 mai 2001, l'Office des poursuites et des faillites a mis l'immeuble, estimé à 880'000 fr., aux enchères publiques et l'a adjugé pour 650'000 fr. à X._ SA , à laquelle la Banque cantonale de Genève avait cédé deux créances, garanties par gage, à l'encontre de A._, sous réserve que celle-ci obtienne l'autorisation d'acquérir le bien-fonds. Le 5 juin 2001, la Commission foncière agricole du canton de Genève (ci-après: la Commission foncière) a délivré l'autorisation d'acquérir à l'adjudicataire, sans faire notifier sa décision à A._, ni à B._. B. Faisant valoir qu'il avait appris que l'adjudicataire s'était faussement prétendue exploitante agricole, A._ et B._ ont, d'une part, recouru au Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif) contre l'autorisation d'acquérir délivrée par décision du 5 juin 2001 et, d'autre part, saisi la Commission foncière d'une demande de révocation de cette autorisation et de rectification du registre foncier. Par décision du 25 août 2004, la Commission foncière a, "statuant sur incident", déclaré que les intéressés n'avaient pas la qualité de partie et intervenaient à la procédure de révocation en tant que dénonciateurs et, "statuant au fond", ordonné différentes mesures d'instruction. Contre cette décision niant leur qualité de partie, A._ et B._ ont interjeté un second recours au Tribunal administratif. Par arrêt du 10 mai 2005, le Tribunal administratif, qui a joint les deux procédures, a déclaré irrecevable le recours dirigé contre l'octroi de l'autorisation d'acquérir du 5 juin 2001, les recourants n'ayant pas la qualité pour recourir contre la décision d'autorisation d'acquérir, et a rejeté le recours exercé contre la décision du 25 août 2004 leur niant la qualité de partie, les intéressés étant de simples dénonciateurs. Le Tribunal fédéral a rejeté le recours de A._ et B._ (arrêt 5A.21/2005 du 17 novembre 2005). C. Par décision du 29 août 2006, la Commission foncière a révoqué sa décision du 5 juin 2001 autorisant la vente de la parcelle en cause à X._ SA, celle-ci l'ayant obtenue en fournissant de fausses indications. Le Tribunal administratif a rejeté le recours de X._ SA, par arrêt du 5 juin 2007. Il a renvoyé la cause à la Commission foncière afin que celle-ci détermine s'il existait des tiers de bonne foi dont les droits seraient lésés par la rectification au registre foncier, soit par la radiation de l'inscription mentionnant X._ SA comme propriétaire de la parcelle. Après instruction, la Commission foncière a jugé, le 29 janvier 2008, que la rectification du registre foncier léserait les droits de la Banque Migros, tiers de bonne foi et a annulé sa décision du 29 août 2006 révoquant celle du 5 juin 2001. Le 20 février 2008, le Service de l'agriculture du canton de Genève (ci-après: le Service de l'agriculture) a attaqué cette décision auprès du Tribunal administratif, recours qu'il a retiré le 13 mai 2008. Par mémoire du 23 mai 2008, A._ et B._ ont recouru contre la décision du 29 janvier 2008 de la Commission foncière invoquant la nullité absolue de cette décision. Le 20 janvier 2009, le Tribunal administratif a déclaré irrecevable le recours des intéressés. Le Tribunal fédéral avait précédemment jugé que les recourants n'avaient pas la qualité pour recourir contre la décision d'octroi de l'autorisation d'acquérir et n'avaient pas non plus la qualité de partie dans le cadre de la procédure en révocation de cette autorisation. Partant, ils n'avaient pas la qualité pour recourir contre la décision du 29 janvier 2008 de la Commission foncière. Le fait que les recourants invoquaient la nullité absolue de la décision litigieuse n'y changeait rien car eut-il encore fallu qu'ils "aient la qualité pour le faire". D. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent au Tribunal fédéral, avec suite de frais et dépens, d'annuler l'arrêt du Tribunal administratif du 20 janvier 2009, puis de constater la nullité de la décision du 29 janvier 2008 de la Commission foncière, d'ordonner la rectification du registre foncier du canton de Genève en ce sens que l'inscription de X._ SA en tant que propriétaire de la parcelle ****, feuille ** de la commune de C._, doit être radiée; subsidiairement, de renvoyer la cause au Tribunal administratif pour une nouvelle décision dans le sens des considérants. Ils invoquent, notamment, un déni de justice formel, le Tribunal administratif ayant retenu de manière incorrecte qu'ils n'avaient pas qualité pour recourir. X._ SA s'en rapporte à justice quant à la recevabilité du recours. Elle conclut, sous suite de frais et dépens, au rejet du recours et à la confirmation de l'arrêt attaqué. Le Tribunal administratif s'en rapporte également à justice quant à la recevabilité du recours et persiste dans les considérants et le dispositif de son arrêt. L'Office fédéral de la justice adhère au dispositif et aux considérants de l'arrêt attaqué et demande le rejet du recours.