Faits : A. B.A._ et A.A._ sont propriétaires, depuis le 3 octobre 2001, de la parcelle n° ccc, sise en zone agricole, à l'extrémité de la commune de D._, en bordure de la commune voisine de E._, dans le hameau de F._. La parcelle susmentionnée, d'une surface totale de 1'826 m 2, comporte trois bâtiments formant actuellement une maison d'habitation - composée de deux logements -, dans laquelle les époux A._ habitent depuis 1995. À environ 50 m de la maison, au bord de la route de F._, se trouve un couvert à véhicules et, à environ 100 m, une ancienne cave à fromage semi-enterrée sous l'emprise d'un grand chêne. En 2009, B.A._ et A.A._ ont déposé une première demande d'autorisation portant sur l'extension de leur habitation auprès de l'ancien département des constructions et des technologies de l'information (actuellement le département de l'aménagement, du logement et de l'énergie [ci-après: le DALE ou le département]). Leur requête portait plus précisément sur la construction d'un logement annexe, auquel serait rattachée la cave semi-enterrée, préalablement démolie et déplacée à cette fin. Le 8 janvier 2010, le département a refusé d'enregistrer la demande des prénommés, considérant que la construction d'un nouveau logement sur une ancienne annexe ne comportant pas de surface habitable apparaissait d'emblée contraire à l'affectation agricole de la zone et à l'art. 27C de la loi cantonale d'application de la loi fédérale sur l'aménagement du territoire du 4 juin 1987 (LaLAT; RS/GE L 1 30). A la demande de B.A._ et A.A._, le projet a néanmoins été enregistré formellement. Le 3 juin 2010, pour les mêmes motifs que ceux retenus le 8 janvier 2010, le département a refusé l'autorisation requise. B. A la suite de divers échanges entre un juriste du département et les prénommés, ces derniers ont, le 13 janvier 2012, déposé une demande définitive ayant pour objet l'extension de la maison individuelle; cet agrandissement consistait en la création d'un logement annexe indépendant sur rez avec un sous-sol, comprenant une chambre, un salon, une salle à manger, une salle de bain, une cave, une buanderie et deux salles de rangement. Ce projet impliquait également la démolition de la cave semi-enterrée située sous l'emprise du grand chêne, ainsi que le déplacement du couvert à véhicules de quelques mètres à l'ouest de celui-ci. Dans le cadre de l'instruction de cette dernière demande, les services consultés et la commune de D._ on émis des préavis favorables. Le Service des plans d'affectation et requêtes a en revanche préavisé négativement le projet, considérant ce dernier contraire à l'art. 27C LaLAT, l'annexe envisagée devant nécessairement être comptabilisée comme une nouvelle surface bâtie à l'extérieur du volume bâti existant. Par décision séparée du 23 mai 2013, le département a autorisé la démolition de la cave à fromage et du couvert à voitures. En revanche, sur la base notamment d'un procès-verbal du 2 avril 1993 relatif à la vente aux enchères de la parcelle en cause, le département a estimé que l'usage non agricole du bâtiment d'habitation au 1 er janvier 1972 n'était pas démontré, de sorte que le projet ne pouvait être autorisé. Ainsi par décision du 5 juin 2013 et en dépit des différents éléments et pièces produits par les prénommés, le département a refusé l'agrandissement de leur maison d'habitation. Il ressort notamment de cette décision qu'en raison de transformations (rehaussement du toit) effectuées par le passé et de l'affectation encore conforme à la zone agricole, une autorisation de construire fondée sur l'art. 24c de la loi fédérale sur l'aménagement du territoire du 22 juin 1979 (LAT; RS 700) ne pouvait être délivrée. Le département a en outre considéré que l'identité de la construction au sens de l'art. 42 de l'ordonnance sur l'aménagement du territoire (OAT; RS 700.1) n'était pas respectée et que l'extension projetée n'était nécessaire ni à un usage d'habitation répondant aux normes usuelles ni à un assainissement énergétique; elle ne visait pas non plus une meilleure intégration dans le paysage. C. B.A._ et A.A._ ont recouru contre cette décision auprès du Tribunal administratif de première instance de la République et Canton de Genève (ci-après: le TAPI). Faute de plans décrivant l'état au 1er juillet 1972, celui-ci a estimé qu'on ne pouvait déterminer si, à cette date, le bâtiment avait été érigé ou transformé légalement; la réalisation des conditions d'une autorisation dérogatoire en zone agricole n'étant ainsi pas démontrée, le TAPI a rejeté le recours par jugement du 27 août 2014. Le 26 septembre 2014, B.A._ et A.A._ ont contesté cette décision devant la Chambre administrative de la Cour de justice de la République et Canton de Genève (ci-après: la Cour de justice), qui a rejeté leur recours par arrêt du 31 mars 2015. A titre préalable, l'instance précédente a rappelé que les art. 24c LAT, 41 et 42 OAT ont fait l'objet de modifications entrées en vigueur le 1er novembre 2012 (RO 2012 5535 et 5537). Appliquant le nouveau droit à la demande d'autorisation litigieuse, la Cour de justice a estimé qu'aucune des conditions alternatives définies par le nouvel art. 24c al. 4 LAT n'était réalisée, de sorte qu'une modification extérieure du bâtiment ne pouvait être autorisée. D. Agissant par la voie du recours en matière de droit public, B.A._ et A.A._ demandent principalement au Tribunal fédéral d'annuler l'arrêt de la Cour de justice, le jugement du TAPI ainsi que la décision du département du 5 juin 2013; subsidiairement, ils concluent à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants. Le 11 juin 2015, les recourants ont spontanément déposé des observations complémentaires ainsi que diverses annexes. La Cour de justice persiste dans les considérants et le dispositif de son arrêt. Le DALE conclut au rejet du recours. Egalement appelé à se déterminer, l'Office fédéral du développement territorial (ARE) demande aussi le rejet du recours. Les recourants ont répliqué.