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.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1.1 p. 3; <ref-ruling> consid. 1 p. 444 et les arrêts cités).
1.1 En vertu de l'<ref-law>, a qualité pour former un recours en matière de droit public quiconque a pris part à la procédure devant l'autorité précédente ou a été privé de la possibilité de le faire (lettre a), est particulièrement atteint par la décision attaquée (lettre b) et a un intérêt digne de protection à son annulation ou à sa modification (lettre c).
Les recourants ont qualité pour recourir au sens de cette disposition. Ils ont notamment un intérêt digne de protection à demander l'annulation de l'arrêt attaqué afin d'obtenir qu'il soit statué sur le fond de leur cause; cela indépendamment et sans préjudice du motif d'irrecevabilité retenu en procédure administrative, qui constitue l'objet de la contestation devant le Tribunal fédéral, et à l'exclusion du fond de l'affaire (<ref-ruling> consid. 4 p. 241 et les arrêts cités).
1.2 Dans une procédure administrative, l'auteur d'un recours déclaré irrecevable pour défaut de qualité pour agir est habilité à contester l'arrêt d'irrecevabilité par un recours en matière de droit public (arrêt 1C_52/2008 du 2 juin 2008 consid. 1.2) lorsque l'arrêt au fond de l'autorité intimée aurait pu être déféré au Tribunal fédéral par cette voie (<ref-ruling> consid. 1 p. 500; <ref-ruling> consid. 1b p. 502). Tel est le cas en l'espèce. En effet, en matière d'autorisation d'acquérir une entreprise ou un immeuble agricole (cf. art. 61 de la loi fédérale du 4 octobre 1991 sur le droit foncier rural [ci-après LDFR; RS 211.412.11]), les décisions prises sur recours par l'autorité cantonale de dernière instance sont sujettes au recours en matière de droit public au Tribunal fédéral, conformément aux <ref-law> (<ref-law>).
1.3 Pour le surplus, dirigé contre une décision finale (<ref-law>) rendue dans une cause de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 lettre d LTF), le recours ne tombe pas sous le coup d'une des exceptions mentionnées à l'<ref-law>. Déposé en temps utile (<ref-law>) et en la forme prévue (<ref-law>) par les destinataires de la décision attaquée, il est en principe recevable.
2. Comme susmentionné, le Tribunal administratif a considéré que les recourants n'avaient pas la qualité pour recourir contre la décision du 29 janvier 2008. Partant, il a déclaré le recours des intéressés irrecevable. Dès lors, devant le Tribunal de céans, les griefs ne peuvent porter, outre sur les droits de partie des recourants, que sur le refus d'entrer en matière sur le recours. Ainsi, en tant que les griefs et les conclusions des recourants ont trait à la décision d'annulation du 29 janvier 2008, ils sont irrecevables.
3. 3.1 Dans un premier grief, les recourants invoquent une constatation des faits manifestement inexacte (cf. <ref-law>). Ils se plaignent tout d'abord de ce que le Tribunal administratif aurait omis de mentionner qu'il avait confirmé l'annulation de l'autorisation d'acquérir pour fraude à la loi. Ils précisent ensuite que l'arrêt attaqué n'indiquerait pas que le conservateur du registre foncier a été entendu lors d'une comparution personnelle. Finalement, cet arrêt ne donnerait pas les détails du retrait du recours interjeté par le Service de l'agriculture à l'encontre de la décision du 29 janvier 2008.
3.2 Selon l'<ref-law>, le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte ou en violation de droit au sens de l'<ref-law>, et si la correction du vice est susceptible d'influer sur le sort de la cause. Or, les faits susmentionnés qui auraient été omis ou mal constatés n'ont pas trait au refus du Tribunal administratif d'entrer en matière sur le recours qui seul constitue l'objet du litige devant le Tribunal fédéral. Partant, la correction de ces faits n'aurait aucune influence sur la sort de la cause. Le grief doit ainsi être rejeté.
4. 4.1 Les recourants estiment qu'en déclarant leur recours irrecevable pour défaut de qualité de partie, le Tribunal administratif a commis un déni de justice. Selon eux, quiconque pouvant demander que soit constatée la nullité absolue d'un acte, ledit Tribunal devait entrer en matière. Or, la décision du 29 janvier 2008, annulant la décision du 29 août 2006 laquelle révoquait celle du 5 juin 2001, serait nulle car, notamment, la Commission foncière n'était pas compétente pour annuler sa propre décision du 29 août 2006.
4.2 La question de savoir si, malgré l'irrecevabilité du recours des intéressés devant le Tribunal administratif, celui-ci aurait dû se prononcer sur la nullité invoquée de la décision du 29 janvier 2008 peut rester ouverte. En effet, le recours doit de toute façon être rejeté comme exposé ci-après.
Le Tribunal fédéral a jugé, dans son arrêt du 17 novembre 2005, que c'était à bon droit que le Tribunal administratif avait, d'une part, nié la qualité pour recourir des intéressés à l'encontre de la décision du 5 juin 2001 de la Commission foncière autorisant X._ SA à acquérir l'immeuble adjugé et, d'autre part, rejeté leur recours contre la décision du 25 août 2004 de la même Commission leur niant la qualité de partie et confirmant qu'ils étaient de simples dénonciateurs dans la procédure en révocation de l'autorisation d'acquérir.
Lorsqu'ils ont appris que la Commission foncière avait rendu sa décision du 29 janvier 2008 annulant la révocation de l'autorisation d'acquérir prononcée le 29 août 2001, "les recourants sont allés trouver le Service de l'agriculture" afin que celui-ci recourt contre ladite décision, laquelle était "entachée de vices graves" (recours du 23 mai 2008 au Tribunal administratif p. 3). Ledit Service a recouru le 20 février 2008. Ainsi, au vu de l'arrêt du Tribunal fédéral susmentionné leur ayant nié la qualité pour recourir contre l'octroi d'autorisation d'acquérir ainsi que la qualité de partie dans la procédure en révocation, les intéressés n'avaient pas recouru initialement à l'encontre de la décision de la Commission foncière du 29 janvier 2008. Toutefois, le Service de l'agriculture a retiré son recours en date du 13 mai 2008. Les intéressés ont alors déposé un recours le 23 mai 2008 invoquant la nullité de la décision du 29 janvier 2008. Or, les recourants, qui n'étaient pas partie à la procédure qui a abouti à la décision du 29 janvier 2008, avaient trente jours pour déposer leur recours à partir du moment où ils avaient eu connaissance de la décision (cf. art. 63 al. 1 let. a de la loi genevoise du 12 septembre 1985 sur la procédure administrative, art. 63 al. 4 de la même loi, dans sa teneur en vigueur jusqu'au 31 décembre 2008, et <ref-law>). Le dossier ne dit pas à quelle date les intéressés ont eu connaissance de la décision du 29 janvier 2008, ni quand ils ont contacté le Service de l'agriculture afin qu'il recourt. Ledit Service ayant déposé son recours le 20 février 2008, c'est au plus tard à cette date que les recourants ont eu connaissance de la décision en cause. Ils avaient ainsi trente jours dès celle-ci pour agir. Leur recours devant le Tribunal administratif n'ayant été déposé que le 23 mai 2008, il était tardif.
Les recourants se prévalaient de la nullité de la décision du 29 janvier 2008. Or, la nullité des actes administratifs viciés est l'exception, l'annulation - qui ne peut être invoquée que par des personnes déterminées, dans les formes et les délais prescrits - étant la règle (RDAF 2005 I 62 consid. 3, I 688/03). D'après la jurisprudence, la nullité d'une décision, laquelle n'est prononcée que dans des cas exceptionnels, n'est admise que si le vice dont elle est entachée est particulièrement grave, est manifeste ou du moins facilement décelable et si, en outre, la constatation de la nullité ne met pas sérieusement en danger la sécurité du droit. Des vices de fond n'entraînent qu'à de rares exceptions la nullité d'une décision. De graves vices de procédure sont en revanche des causes de nullité (<ref-ruling> consid. 3.3 p. 434). Si l'incompétence qualifiée de l'autorité qui a rendu la décision est un motif de nullité (<ref-ruling> consid. 4a p. 135; <ref-ruling> consid. 3.1 p. 27), tel n'était clairement pas le cas en l'espèce puisque c'est le Tribunal administratif lui-même, dans son arrêt du 5 juin 2007, qui avait ordonné à la Commission foncière de statuer à nouveau sur le maintien ou la révocation de l'autorisation d'acquérir de X._ SA, après avoir pris les renseignements pertinents relatifs à l'existence de tiers de bonne foi. A cet égard, l'art. 10 let. b de la loi genevoise du 16 décembre 1993 d'application de la loi fédérale sur le droit foncier rural (RS/GE M 1 10) dispose que cette Commission est compétente en matière d'autorisation pour l'acquisition d'une entreprise ou d'un immeuble agricole. Or, en vertu du principe du parallélisme des formes, qui consiste à soumettre la révision d'un acte à la même procédure que son adoption, la Commission foncière est incontestablement compétente pour révoquer une autorisation d'acquérir (cf., à titre d'exemple, l'art. 5 al. 1 et al. 2 let. d de la loi vaudoise du 13 septembre 1993 d'application de la loi fédérale du 4 octobre 1991 sur le droit foncier rural [RS/VD 211.42] qui prévoit expressément la compétence de la Commission foncière rurale en matière d'octroi et de révocation d'autorisation d'acquérir). Quant aux autres motifs de nullité invoqués par les recourants, soit, lors de la procédure devant la Commission foncière, l'absence de réponse écrite du conservateur du registre foncier à la suite de l'interpellation de dite Commission et la comparution personnelle du conservateur devant cette Commission, ainsi que le fait que la banque en cause ne serait pas un tiers de bonne foi au sens de l'<ref-law>, ils ne remplissent pas le critère de vice particulièrement grave.
Se prévaloir de la nullité de la décision du 29 janvier 2008 de la Commission foncière pour des motifs qui ne peuvent à l'évidence être qualifiés de très graves, alors que la qualité de partie avait initialement été niée aux intéressés dans la procédure en cause et que le délai légal de recours à l'encontre de la décision susmentionnée était échu, est contraire au principe de la bonne foi qui commande aux autorités comme aux particuliers de s'abstenir, dans les relations de droit public, de tout comportement abusif (Häfelin/Müller/Uhlmann, Allgemeines Verwaltungsrecht, 5ème éd., 2006, n. 623). Dès lors, invoquer, devant le Tribunal fédéral, un déni de justice dans ces conditions viole également les règles de la bonne foi. Partant, le recours doit être rejeté.
5. Au vu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable. Succombant, les recourants doivent supporter les frais judiciaires (art. 65 et 66 al. 1 LTF) et n'ont pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge des recourants solidairement entre eux.
3. Le présent arrêt est communiqué aux mandataires des parties, au Tribunal administratif du canton de Genève et au Département fédéral de justice et police, ainsi qu'à la Commission foncière agricole du canton de Genève pour information.
Lausanne, le 14 septembre 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
R. Müller E. Kurtoglu-Jolidon