Faits: A. Y._ est propriétaire de parcelles sises sur la Commune de X._. Ces parcelles jouxtent la parcelle no **** d'une surface de **** m2, sise en zone agricole. La parcelle ****, estimée à 85'000 fr., a été mise aux enchères par l'office des poursuites le 2 novembre 2007. Plusieurs personnes ont enchéri, dont Y._, Z._ SA et la Commune de X._. L'immeuble a été adjugé à Z._ SA, créancière gagiste à la suite d'une cession de créance, pour 1'130'000 fr. Le 12 novembre 2007, l'adjudicataire a requis l'autorisation d'acquérir l'immeuble en question auprès de la Commission foncière agricole du canton de Genève (ci-après: la Commission foncière). Le même jour, la Commune de X._ a demandé à pouvoir intervenir dans la procédure d'octroi d'autorisation. Y._ a fait de même le 21 novembre 2007. Par décision du 24 juin 2008, la Commission foncière a rejeté leur demande d'intervention. Le Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif) a rejeté le recours de Y._ et de la Commune de X._ par arrêt du 13 janvier 2009. Il a relevé que les recourants, qui voulaient acquérir la parcelle dans le but de la protéger de tout projet immobilier et de lui conserver son caractère de site exceptionnel, ne revêtaient aucune des qualités énumérées par l'art. 83 al. 2 et 3 de la loi fédérale du 4 octobre 1991 sur le droit foncier rural (LDFR ou la loi fédérale sur la droit foncier rural; RS 211.412.11) et n'étaient pas au bénéfice d'un intérêt digne de protection à ce que Z._ SA n'obtienne pas l'autorisation d'acquérir la parcelle en cause. Au vu du but poursuivi par la loi fédérale sur le droit foncier rural et de l'art. 64 al. 1 let. g LDFR, il y avait lieu de considérer que la qualité d'adjudicataires évincés des recourants et leur intérêt à l'acquisition de la parcelle n'étaient pas des éléments suffisants pour admettre leur qualité de partie. Partant, c'était à juste titre que la Commission foncière la leur avait déniée. B. Y._ et la Commune de X._ ont déposé un recours en matière de droit civil auprès de la IIème Cour de droit civil du Tribunal fédéral. Ils lui demandent, sous suite de frais et dépens, d'annuler le jugement du Tribunal administratif du 13 janvier 2009, ainsi que la décision de la Commission foncière du 24 juin 2008 et de leur reconnaître le droit d'intervenir dans la procédure d'autorisation devant la Commission foncière, subsidiairement de renvoyer la cause au Tribunal administratif pour qu'il statue dans ce sens. 