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.

Considérant en droit:
1. Dirigé contre une décision rendue dans le domaine du droit public des constructions, le recours est recevable comme recours en matière de droit public conformément aux <ref-law>, aucune des exceptions prévues à l'<ref-law> n'étant réalisée. Les recourants ont pris part à la procédure de recours devant le Tribunal cantonal et sont particulièrement touchés par l'arrêt attaqué, qui confirme l'autorisation de construire, sur la parcelle voisine de la leur, un garage qui condamnerait un accès à leur bien-fonds. Ils ont donc la qualité pour agir au sens de l'<ref-law>. Pour le surplus, interjeté en temps utile et dans les formes requises contre une décision finale prise en dernière instance cantonale non susceptible de recours devant le Tribunal administratif fédéral, le recours est recevable au regard des art. 42, 86 al. 1 let. d, 90 et 100 al. 1 LTF.
2. A l'appui de leurs déterminations, les intimés ont produit deux nouvelles pièces, à savoir des courriers des 19 mai et 9 juin 2008. Ils n'expliquent cependant pas pourquoi ils auraient été empêchés de déposer ces documents devant l'instance précédente, ni en quoi ceux-ci résulteraient de la décision attaquée. Ces preuves nouvelles sont donc irrecevables (<ref-law>; <ref-ruling> consid. 3 p. 395).
3. Dans un premier grief, les recourants se plaignent d'une violation de l'art. 17 al. 2 Titre final CC.
3.1 Aux termes de l'art. 17 al. 1 Titre final CC, les droits réels existant lors de l'entrée en vigueur du code civil sont maintenus, sous réserve des règles concernant le registre foncier. L'art. 17 al. 2 Titre final CC précise que "si une exception n'est pas faite dans le présent code, l'étendue de la propriété et des autres droits réels est néanmoins régie par la loi nouvelle dès son entrée en vigueur". Enfin, à teneur de l'art. 17 al. 3 Titre final CC, les droits réels dont la constitution n'est plus possible à teneur de la loi nouvelle continuent à être régis par la loi ancienne.
3.2 Tel qu'il est formulé, le grief des recourants ne permet pas de comprendre pourquoi l'art. 17 al. 2 Titre final CC serait applicable au présent litige, ni en quoi il aurait été violé. Il n'est en effet pas question en l'espèce de l'application de la loi nouvelle à des droits réels antérieurs à son entrée en vigueur. A bien vouloir les comprendre, les recourants soutiennent qu'une ancienne disposition de la LRoutes antérieure à l'entrée en vigueur du Code civil - l'art. 24 aLRoutes, devenu l'art. 28 aLroutes, abrogé depuis - serait applicable. Cette disposition prévoyait que lorsqu'un chemin avait été ouvert au public pendant cinq ans au moins, il ne pourrait plus être fermé qu'avec l'autorisation du Conseil d'Etat. Les recourants se prévalent à cet égard de l'ATF 71 I 433, qui évoquait la possibilité - formulée de manière particulièrement prudente - que l'art. 28 aLRoutes ait fait acquérir à l'Etat de Genève un droit de passage sur une parcelle ou du moins le droit de refuser à son propriétaire l'autorisation de fermer son chemin. Contrairement à ce que soutiennent les recourants, il ne découle pas de cet arrêt que la disposition en cause permet de fonder la création d'un droit réel. De plus, cette disposition ayant été abrogée depuis, elle ne saurait s'appliquer au cas d'espèce. Quoi qu'il en soit, les recourants ne démontrent pas une application arbitraire du droit cantonal à cet égard, conformément aux exigences minimales d'allégation et de motivation déduites de l'<ref-law>, respectivement de l'<ref-law> (<ref-ruling> consid. 1.4 p. 254 s.). De plus, le Tribunal administratif a retenu qu'aucune servitude de passage n'avait été constituée sur la parcelle n° 7266 et que ni le département, ni la commune, n'avaient fait état d'un quelconque titre ou acte d'affectation qui incorporerait le chemin litigieux au domaine public. Le caractère arbitraire de ces constatations n'étant pas davantage démontré, il y a lieu de constater que l'existence d'un droit réel n'a pas été établie. En définitive, on ne voit pas en quoi l'art. 17 Titre final CC serait applicable, de sorte que le grief tiré de la violation de l'art. 17 al. 2 Titre final CC ne peut qu'être rejeté, dans la mesure où il est recevable.
4. Les recourants se plaignent également d'une application arbitraire de la LRoutes et de la loi cantonale sur les constructions et les installations diverses (LCI; RSG L 5 05).
4.1 Appelé à revoir l'application ou l'interprétation d'une norme sous l'angle de l'arbitraire (pour une définition de l'arbitraire, cf. <ref-ruling> consid. 3.1 p. 153; <ref-ruling> consid. 5.1 p. 17 et les arrêts cités), le Tribunal fédéral ne s'écarte de la solution retenue par l'autorité cantonale de dernière instance que si celle-ci apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motifs objectifs et en violation d'un droit certain. En revanche, si l'application de la loi défendue par l'autorité cantonale ne s'avère pas déraisonnable ou manifestement contraire au sens et au but de la disposition ou de la législation en cause, cette interprétation sera confirmée, même si une autre solution - éventuellement plus judicieuse - paraît possible (<ref-ruling> consid. 4.1 p. 133; <ref-ruling> consid. 5.1 p. 260 s. et les arrêts cités).
4.2 A la lecture de l'écriture de recours, on peine à discerner quelles dispositions de la LRoutes sont précisément visées par le grief d'arbitraire. En substance, les recourants reprochent au Tribunal administratif de s'être fondé sur l'art. 35 al. 1 LRoutes pour rejeter leur grief fondé sur la fermeture d'une voie publique. Selon cette disposition, sont soumis à la surveillance du département non seulement les chemins privés immatriculés comme tels au registre foncier mais également toute parcelle de terrain présentant le caractère d'un passage ouvert au public. Dans la mesure où ils n'invoquaient pas les dispositions de la LRoutes relatives aux chemins privés, les recourants prétendent que l'application de l'art. 35 LRoutes serait "hors-sujet" et partant arbitraire. Cela étant, le Tribunal administratif a mentionné cette disposition pour répondre à l'argument des recourants selon lequel le garage litigieux fermait une voie publique. Dès lors qu'il est établi que le chemin en question est situé sur des parcelles privées, on ne voit pas quelles autres dispositions que les art. 35 ss LRoutes pourraient entrer en considération. Pour le surplus, les critiques des recourants se focalisent sur un prétendu "revirement" quant à la qualification juridique du chemin litigieux, ce qui n'a pas sa place dans la démonstration d'une application arbitraire de la LRoutes. Quant aux critiques portant sur l'art. 7 LRoutes, elles peuvent être rejetées ne serait-ce que parce qu'il n'est pas établi que le chemin litigieux constitue une "voie ouverte au public" au sens de cette disposition. Il en va de même en ce qui concerne les art. 56 et 57 LRoutes, qui comprennent des règles sur les voies publiques.
4.3 Les recourants se plaignent également d'une application arbitraire de l'art. 3 al. 3 RALCI, qui prévoit que la surface totale des constructions de peu d'importance ne doit pas excéder 8% de la surface de la parcelle. La parcelle des intimés ayant une superficie de 496 m2, la surface totale des constructions de peu d'importance ne devrait pas dépasser 39,68 m2. Or, en plus du garage litigieux, d'une surface de 39 m2, le Tribunal administratif aurait arbitrairement omis de prendre en compte la verrière reliant les deux bâtiments des intimés. Le Tribunal administratif considère toutefois que cette liaison vitrée "fait corps avec les bâtiments qu'elle relie" et qu'elle est "partie intégrante des surfaces habitables dont elle constitue l'entrée", de sorte qu'elle ne doit pas être prise en compte au titre de construction de peu d'importance. Vu la configuration des lieux, il n'est pas insoutenable ni manifestement choquant de retenir que cette verrière constitue le hall d'entrée des deux bâtiments, avec lesquels il forme une certaine unité. Dès lors, même si le raisonnement de l'arrêt attaqué peut être discuté et s'il n'est pas exclu qu'une autre appréciation ait été possible, cela ne suffit pas pour considérer que la solution retenue est arbitraire au sens de la jurisprudence susmentionnée.
5. Enfin, les recourants se plaignent encore d'une violation de l'art. 29 Cst. et de l'interdiction du déni de justice formel. Ils prétendent que le Tribunal administratif a refusé d'entrer en matière sur la question d'un escalier en béton sis sur la parcelle litigieuse et qui constituerait selon eux également une construction de peu d'importance au sens de l'art. 3 al. 3 RALCI. Il est vrai que le recours déposé auprès du Tribunal administratif le 2 mai 2008 mentionnait cet escalier en béton. Cette mention prenait cependant place dans une écriture d'une trentaine de pages comprenant de nombreux griefs et allégués, qui portaient également sur un portail d'entrée, des piliers en béton ou un barbecue. Ces éléments étaient évoqués dans le cadre d'une argumentation visant apparemment à démontrer que l'autorisation de construire contestée ne pouvait pas être délivrée dans le cadre d'une "procédure d'APA". Il n'apparaît dès lors pas que l'escalier en béton ait fait l'objet d'un grief particulier, sur lequel le Tribunal administratif aurait dû se prononcer sous peine de déni de justice. En tous les cas, les recourants ne le démontrent pas. Ce moyen doit donc lui aussi être rejeté.
6. Il s'ensuit que le recours doit être rejeté, dans la mesure de sa recevabilité. Les recourants, qui succombent, doivent supporter les frais de la présente procédure (<ref-law>). Ils verseront en outre une indemnité à titre de dépens aux intimés, qui obtiennent gain de cause avec l'assistance d'un avocat (<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.
3. Une indemnité de 2'000 fr. est allouée aux intimés à titre de dépens, à la charge des recourants.
4. Le présent arrêt est communiqué aux mandataires des parties, ainsi qu'au Département des constructions et des technologies de l'information et au Tribunal administratif du canton de Genève.
Lausanne, le 27 avril 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener