Faits: A. C._ et D._ sont copropriétaires de la parcelle n° 7266 du registre foncier de Bernex (GE). Sis en zone à bâtir, ce bien-fonds d'une surface de 496 m2 supporte deux bâtiments d'habitation reliés par une construction de type verrière. Le 31 janvier 2005, ils ont requis l'autorisation de construire un garage sur ce terrain. Conformément aux exigences de la Commission cantonale des monuments, de la nature et des sites, les dimensions du projet ont été fixées à 2,5 m pour la hauteur, 6 m pour la largeur et 6,5 m pour la longueur. Par décision du 5 janvier 2006, le Département des constructions et des technologies de l'information du canton de Genève (ci-après: le département) a délivré l'autorisation de construire requise. A._ et B._, copropriétaires de la parcelle voisine n° 2467, ont recouru contre cette autorisation auprès de la Commission cantonale de recours en matière de construction (ci-après: la commission de recours). Leur parcelle supporte un bâtiment inscrit à l'inventaire cantonal des immeubles dignes d'être protégés et elle bénéficie d'une servitude de passage pour piétons grevant la parcelle n° 4463 sise au nord. L'accès à la parcelle de A._ et B._ se faisait également par un chemin privé en forme de fer à cheval, rejoignant la route de Bernex à l'ouest par la parcelle n° 2468 et à l'est par la parcelle n° 7266 de C._ et D._. Le garage litigieux serait érigé sur ce chemin. A._ et B._ sont également propriétaires d'une petite parcelle n° 7230, utilisée comme place de stationnement. Ce bien-fonds est situé à l'est de la parcelle n° 7266, dans le prolongement du chemin qui serait fermé par le projet contesté. Leur recours ayant été rejeté, A._ et B._ ont saisi le Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif), qui a admis le recours par arrêt du 6 février 2007, au motif que certains préavis faisaient défaut. B. Après un complément d'instruction, le département a délivré l'autorisation de construire requise, par décision du 2 août 2007. A._ et B._ ont contesté cette décision devant la commission de recours, en se plaignant notamment d'une violation des dispositions applicables en cas de fermeture d'une voie publique. Leur recours a été rejeté par décision du 10 mars 2008. La commission de recours a notamment considéré que le chemin passant sur la parcelle de C._ et D._ - et sur lequel le garage litigieux devait être érigé - n'était pas une voie publique au sens de l'art. 7 al. 1 et 2 de la loi cantonale sur les routes du 28 avril 1967 (LRoutes; RSG L 1 10). A._ et B._ ont recouru contre cette décision auprès du Tribunal administratif. Ils alléguaient en particulier que le garage litigieux serait construit sur l'emprise d'un chemin public et qu'il modifierait une voie de circulation communale, ce qui nécessitait une autorisation fondée sur l'art. 7 LRoutes. Ils se plaignaient également d'une violation des dispositions cantonales sur les constructions de peu d'importance. Le Tribunal administratif a rejeté ce recours, par arrêt du 11 novembre 2008. Il a considéré qu'il n'était pas établi que le chemin sur lequel serait construit le garage litigieux était incorporé au domaine public. Par ailleurs, contrairement à ce que soutenaient A._ et B._, la liaison vitrée entre les deux bâtiments de C._ et D._, ainsi que leur barbecue et leur portail d'entrée, ne devaient pas être pris en compte comme constructions de peu d'importance. Seul le garage litigieux devait être pris en considération à ce titre, de sorte que la proportion maximale de 8% prévue par l'art. 3 al. 3 du Règlement d'application de la loi cantonale sur les constructions et installations diverses (RALCI; RSG L 5 05.01) était respectée. C. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent au Tribunal fédéral d'annuler cet arrêt, ainsi que l'autorisation de construire du 2 août 2007. Ils requièrent également l'octroi de l'effet suspensif. Le Tribunal administratif se réfère aux considérants de son arrêt. Le département conclut au rejet du recours, sans présenter d'observations. C._ et D._ se sont déterminés; ils concluent au rejet du recours. ._ et B._ et C._ et D._ ont présenté des observations complémentaires. D. Par ordonnance du 30 janvier 2009, le Président de la Ire Cour de droit public a rejeté la requête d'effet suspensif. 