Faits:
A. En 1956, Z._ a fait édifier une villa sur la parcelle portant alors le n° 10'024 du cadastre de la commune de A._.
Souhaitant valoriser sa propriété, l'intéressée a déposé, en 1989, une demande d'autorisation de construire une deuxième maison, contiguë à la sienne. Pour ce faire, elle a morcelé sa parcelle: une partie comprenait sa villa et la partie sud-est de l'ancien jardin (parcelle n° 1'179); l'autre débutait à l'aplomb de la façade nord-ouest de sa maison et comportait toute la moitié nord-ouest du parc, traversée par une petite route desservant l'immeuble existant depuis la voie publique (parcelle n° 1'180).
Par acte du 3 avril 1989, Z._ a vendu la parcelle n° 1'180 à B._, qui envisageait d'y construire une villa. Ce projet devait entraîner diverses conséquences pour Z._. Sur la façade nord-ouest de son immeuble, contre laquelle la nouvelle construction devait s'appuyer, se trouvaient une fenêtre à l'étage ainsi que la porte du garage, lesquelles allaient être supprimées. Un soupirail destiné à l'aération de la citerne de sa villa, situé au pied de ladite façade, tombait dans la propriété de l'acheteur. L'accès piétonnier à la porte d'entrée de sa maison se faisait au moyen d'un escalier débutant sur la même façade et devait ainsi être modifié. Enfin, l'intéressée perdait la propriété de la route d'accès sise sur la parcelle n° 1'180. Le seul engagement pris par l'acheteur dans l'acte de vente, en contrepartie de ces désagréments, était la prise en charge des frais liés à la construction d'un nouveau couvert pour deux voitures, sur la parcelle n° 1'179. Aucune servitude d'accès à la charge de la parcelle n° 1'180 n'a été constituée à cette occasion. L'autorisation de construire la maison contiguë, délivrée le 18 avril 1989, n'a jamais été utilisée et est devenue caduque par suite de l'écoulement du temps. Le 26 avril 1989, la société C._ SA a acquis la parcelle à construire par voie d'adjudication.
B. Le 23 septembre 1999, Z._ a vendu la parcelle n° 1'179 aux époux X._. Le 23 mars 2007, la Fondation Y._ a acquis la parcelle n° 1'180.
Par décision du 20 novembre 2007, la Fondation Y._ a obtenu du Département des constructions et des technologies de l'information du canton de Genève (ci-après: le DCTI) une autorisation préalable de construire une villa contiguë à celle des époux X._. Le projet visait l'édification d'un immeuble destiné à l'habitation, relié à la maison des époux susnommés par un couvert à véhicule pour deux voitures qui s'adossait à la façade nord-ouest de leur bâtiment. La hauteur de ce garage était suffisamment basse pour permettre la conservation de la fenêtre située à l'étage du bâtiment existant. En revanche, elle entraînait la condamnation de la porte du garage et du soupirail de ventilation de la citerne situés sur ladite façade, ainsi que la suppression de la route d'accès sise sur la parcelle n° 1'180.
Les époux X._ ont recouru contre l'autorisation précitée auprès de la Commission cantonale de recours en matière de constructions du canton de Genève (ci-après: la Commission cantonale). Au cours de la procédure, faisant suite aux objections des recourants, la Fondation Y._ a déposé devant le Département des constructions une demande d'autorisation complémentaire visant à abaisser le couvert à voitures de 2.90 à 2.50 mètres. Cette autorisation a été délivrée le 12 mars 2008 (recte: 7 juillet 2008).
Le 14 avril 2008, la Commission cantonale a rejeté le recours des époux X._ contre l'autorisation préalable du 20 novembre 2007.
Par arrêt du 28 octobre 2008, le Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif) a rejeté le recours des époux X._ contre la décision de la Commission cantonale précitée. Il a considéré pour l'essentiel que la notion d'édification en ordre contigu n'impliquait pas que les constructions devaient être édifiées simultanément. En outre, le couvert à voitures projeté qui devait réunir les deux villas respectait toutes les exigences relatives aux constructions de peu d'importance. Dès lors que l'édification en ordre contigu prévu par le projet litigieux était conforme aux dispositions légales, les articles relatifs aux distances aux limites ne s'appliquaient pas. Les autres griefs des intéressés concernant l'accès à leur villa ne relevaient pas du droit public des constructions mais du droit privé; ils étaient par conséquent irrecevables.
C. Agissant par la voie du recours en matière de droit public, les époux X._ demandent au Tribunal fédéral, sous suite de dépens, d'annuler l'arrêt du Tribunal administratif du 28 octobre 2008 ainsi que l'autorisation de construire publiée en 2007 dans la Feuille d'avis officielle. Ils se plaignent en substance d'une application arbitraire du droit cantonal et d'une mauvaise constatation des faits ainsi que de la violation de l'interdiction du déni de justice formel.
Le Tribunal administratif s'en rapporte à justice quant à la recevabilité du recours et persiste dans les considérants et le dispositif de son arrêt. La Fondation Y._ conclut, sous suite de dépens, à l'irrecevabilité du recours et, subsidiairement, à son rejet ainsi qu'à la confirmation de l'arrêt attaqué. Le DCTI s'en rapporte à justice quant à la recevabilité du recours et, au fond, conclut à son rejet, sous suite de frais.
Les recourants ont répliqué le 12 février 2009.

Considérant en droit:
1. 1.1 Dirigé contre une décision confirmant en dernière instance cantonale l'octroi d'une autorisation préalable de construire fondée sur les normes cantonales de police des constructions, sans qu'aucune des exceptions prévues à l'art. 83 LTF ne soit réalisée, le recours est en principe recevable comme recours en matière de droit public au sens des art. 82 ss LTF.
Les recourants, qui ont pris part à la procédure devant l'autorité précédente, sont particulièrement touchés par l'arrêt attaqué qui autorise la construction, sur la parcelle voisine, d'une villa contiguë à la leur et qui entraînerait certaines restrictions à leurs droits de propriété (cf. <ref-ruling> consid. 1.3.3 p. 253 s.). Ils disposent ainsi de la qualité pour recourir en vertu de l'art. 89 LTF.
1.2 Toutefois, dans la mesure où les intéressés concluent à l'annulation de l'autorisation préalable de construire du 20 novembre 2007, leur recours est irrecevable en raison de l'effet dévolutif du recours déposé auprès du Tribunal administratif (cf. <ref-ruling> consid. 2a p. 302 s.; <ref-ruling> consid. 1c p. 33).
2. Selon l'art. 95 LTF, le recours (ordinaire) au Tribunal fédéral peut être formé notamment pour violation du droit fédéral (let. a), qui comprend les droits constitutionnels des citoyens. En revanche, sauf exceptions non pertinentes en l'espèce (cf. art. 95 let. c à e LTF), la mauvaise application des dispositions cantonales ne peut pas être attaquée directement comme telle devant le Tribunal fédéral (art. 95 LTF a contrario). Il est néanmoins possible de faire valoir que leur mise en oeuvre consacre une violation du droit fédéral, comme la protection contre l'arbitraire au sens de l'art. 9 Cst. ou la garantie d'autres droits constitutionnels (cf. <ref-ruling> consid. 2.3 p. 466). Le Tribunal fédéral n'examine cependant de tels moyens que s'ils sont formulés conformément aux exigences de motivation qualifiées prévues à l'art. 106 al. 2 LTF, qui valent en particulier pour le grief d'arbitraire (cf. <ref-ruling> consid. 2 p. 639 s.; <ref-ruling> consid. 1.4.2 p. 254).
Par conséquent, dans la mesure où le recourant se plaint d'arbitraire dans l'application du droit cantonal, il lui appartient de démontrer par une argumentation circonstanciée et précise en quoi la décision attaquée consacrerait - dans son résultat et pas seulement dans sa motivation - une solution insoutenable ou en contradiction manifeste avec la situation effective, méconnaîtrait gravement une norme ou un principe juridique clair et indiscuté, ou heurterait de manière choquante le sentiment de la justice ou de l'équité (cf. <ref-ruling> consid. 2.2 et 2.3 p. 246 s.; <ref-ruling> consid. 1.3 p. 261 s.; <ref-ruling> consid. 2.1 p. 120 et les arrêts cités).
3. 3.1 Le Tribunal fédéral statue sur la base des faits retenus par l'autorité précédente (art. 105 al. 1 LTF), sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF (cf. art. 105 al. 2 LTF). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente, il doit expliquer de manière circonstanciée en quoi les conditions de l'art. 105 al. 2 LTF seraient réalisées; il doit de plus rendre vraisemblable que la correction du vice est susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF). A ce défaut, un état de fait divergent de celui de la décision attaquée ne peut être pris en compte. L'art. 105 al. 2 LTF trouve application lorsque le Tribunal fédéral, en examinant les griefs soulevés, constate une inexactitude manifeste dans l'état de fait de l'autorité précédente ou lorsque celle-ci saute d'emblée aux yeux (<ref-ruling> consid. 6.2 p. 288).
3.2 Les recourants font valoir que le Tribunal administratif a constaté les faits de façon manifestement incomplète et inexacte. Dans la partie "en fait" de l'arrêt attaqué, la cour cantonale indique que l'autorisation complémentaire, visant à réduire la hauteur du couvert à véhicules de 2.90 à 2.50 mètres, a été délivrée le 12 mars 2008, alors qu'en réalité la décision date du 4 juillet 2008. En outre, le Tribunal administratif ne mentionne pas que cette autorisation fait l'objet d'un recours devant la Commission cantonale et n'est pas entrée en force.
Selon l'extrait de la base de données de la police des constructions relative à l'autorisation de construire complémentaire, annexé par les recourants à leur écriture, l'autorisation en question a été délivrée le 7 juillet 2008 et un recours a été interjeté à son encontre le 11 août 2008. Cette pièce nouvelle peut être prise en considération dans la mesure où elle permet de lever une inexactitude qui ressort de la décision attaquée (cf. art. 99 al. 1 LTF).
Il est manifeste que la date de la délivrance de l'autorisation de construire complémentaire retenue par le Tribunal administratif est erronée. Ceci n'est d'ailleurs pas contesté par les autres parties à la procédure. L'état de fait de l'arrêt attaqué peut donc être rectifié sur ce point.
La cour cantonale ne mentionne certes pas que les époux X._ ont interjeté un recours contre l'autorisation complémentaire et que la pro-cédure est encore pendante. Cet élément n'est cependant pas déterminant pour l'issue du litige (cf. consid. 4 ci-dessous). Par ailleurs, lorsque les recourants affirment que le Tribunal administratif ne pouvait valider l'autorisation de construire préalable tant que l'autorisation complémentaire n'était pas en force, ils soulèvent une question de droit, qui doit être examinée avec le fond. Ce grief est donc irrecevable sous cet angle.
4. D'après les recourants, le Tribunal administratif a appliqué le droit cantonal de façon arbitraire en qualifiant le garage qui doit être réalisé entre les deux maisons de construction de peu d'importance. Le projet initial prévoyait un garage d'une hauteur de 2.95 mètres. Or, selon l'art. 3 al. 3 du règlement d'application du 27 février 1978 de la loi sur les constructions et les installations diverses (RCI; RS/GE L 5 05.01), une construction ne peut être qualifiée de peu d'importance si son gabarit dépasse 2.50 mètres. L'intimée avait certes obtenu, en cours de procédure, une autorisation complémentaire réduisant la hauteur du garage à 2.50 mètres; cette autorisation n'était toutefois pas entrée en force et le Tribunal administratif ne pouvait considérer que le projet avait été corrigé. Il avait ainsi validé une autorisation de construire préalable "totalement illégale".
4.1 L'art. 3 al. 3 RCI a la teneur suivante:
"Sont réputées constructions de peu d'importance, à la condition qu'elles ne servent ni à l'habitation, ni à l'exercice d'une activité commerciale, industrielle ou artisanale, celles dont la surface n'excède pas 50 m2 et qui s'inscrivent dans un gabarit limité par :
a) une ligne verticale dont la hauteur n'excède pas 2,50 m;
b) une ligne oblique faisant avec l'horizontale partant du sommet de la ligne verticale un angle de 30°;
c) une ligne horizontale de faîtage située à 4,50 m du sol au maximum.
..."
D'après le croquis n° V "constructions basses et de peu d'importance" reproduit à la fin du RCI, la ligne verticale correspond à la hauteur de la façade et la ligne de faîtage à l'arête supérieure du toit.
4.2 Les recourants semblent avoir confondu les notions de ligne verticale et de ligne de faîtage. Il ressort en effet des plans figurant au dossier que la ligne verticale du garage soumis à l'autorisation préalable de construire du 20 novembre 2007 est de 2.30 mètres et la ligne de faîtage de 2.95 mètres. Quant au projet de garage ayant obtenu l'autorisation complémentaire du 7 juillet 2008, sa ligne verticale est de 2.00 mètres et sa ligne de faîtage de 2.50 mètres. Dans les deux cas, les conditions de l'art. 3 al. 3 let. a et c RCI sont remplies. Il importe dès lors peu que le projet soit réalisé selon le plan initial ou le plan complémentaire, puisque le garage s'inscrira en tout état de cause dans le gabarit prévu par le règlement. On peut relever qu'il est surprenant que les recourants tentent de tirer parti du fait que l'autorisation complémentaire n'est pas encore entrée en force alors que celle-ci a été requise par l'intimée dans l'unique but de se conformer à leurs désirs. Quoi qu'il en soit, il résulte de ce qui précède que la cour cantonale n'est pas tombée dans l'arbitraire en considérant le garage projeté comme une construction de peu d'importance au sens de l'art. 3 al. 3 RCI. Mal fondé, le grief doit être rejeté.
5. 5.1 Les époux X._ reprochent également au Tribunal administratif d'avoir appliqué le droit cantonal de façon illégale et arbitraire en retenant que des constructions en ordre contigu ne doivent pas nécessairement être réalisées simultanément ni par un seul et même propriétaire ou promoteur immobilier. Les juges cantonaux auraient aussi procédé à une application arbitraire des articles relatifs aux distances aux limites de propriété.
En ce qui concerne le grief d'illégalité, les recourants ne développent aucune motivation à ce sujet, de sorte que leur moyen est irrecevable (cf. consid. 2 ci-dessus). Il en est de même du droit à l'égalité de traitement, dont les recourants ne font qu'alléguer la violation en p. 15 de leur écriture (ch. 77).
5.2 L'art. 58 de la loi genevoise du 14 avril 1988 sur les constructions et les installations diverses (LCI; RS/GE L 5 05) prévoit que les constructions peuvent être édifiées en ordre contigu ou non contigu (al. 1). Est réputée en ordre contigu l'édification de deux maisons au moins, réunies par un mur mitoyen ou par une construction de peu d'importance et disposant chacune de son propre accès de plain-pied (al. 2). Par ailleurs, l'art. 67 LCI interdit l'édification de constructions à la limite de deux propriétés privées (al. 1), à moins qu'elles ne soient édifiées en ordre contigu (al. 2 let. b).
5.3 Le texte clair de l'art. 58 al. 2 LCI ne mentionne pas que des villas contiguës doivent être construites simultanément ni le projet réalisé par un seul et même propriétaire. Une telle exigence ne ressort par ailleurs pas non plus des autres dispositions de la LCI ou d'une pratique de la police genevoise des constructions. Le Tribunal fédéral a déjà eu l'occasion de préciser qu'il n'était pas exigé que les deux maisons soient construites simultanément, ni qu'elles soient alignées et semblables sur le plan architectural (arrêt 1P.757/2005 du 3 avril 2006, consid. 3). Dans ces circonstances, il n'est pas arbitraire de considérer que la villa mitoyenne projetée est une construction en ordre contigu au sens de l'art. 58 al. 2 LCI.
Les recourants font valoir que la solution retenue par la cour cantonale ouvrirait la porte à tous les abus, en ce sens que n'importe quel propriétaire pourrait déposer un projet de construction en ordre contigu adjacent à une maison existante et densifier le coefficient d'utilisation de sa parcelle. Une telle argumentation frise la témérité, puisque, dans le cas d'espèce, la division de la parcelle initiale a été effectuée justement dans le but de permettre la construction d'une villa mitoyenne. Les recourants ne pouvaient l'ignorer en achetant leur villa et devaient pouvoir s'attendre à ce que les propriétaires de la parcelle voisine décident un jour de construire sur leur terrain.
Comme les conditions de l'art. 58 al. 2 LCI sont remplies, c'est sans arbitraire que le Tribunal administratif a considéré que l'art. 67 al. 2 let. b LCI s'appliquait en l'espèce et que, par conséquent, les dispositions relatives aux distances aux limites n'entraient pas en ligne de compte.
6. Les recourants se plaignent de déni de justice dans la mesure où l'arrêt attaqué ne traite pas de la perte de l'accès à leur maison. Le Tribunal administratif aurait dû examiner leurs griefs relatifs à la suppression de l'accès à la route, de la porte de garage et de l'escalier d'entrée, provoquée par le projet litigieux. En effet, comme leur maison n'aura plus d'accès de plain-pied au sens de l'art. 58 al. 2 LCI, il est exclu de considérer la nouvelle villa comme contiguë.
Dans le cas d'espèce, les juges cantonaux ont examiné, certes sommairement, le problème de l'accès à la villa des intéressés. Ils ont finalement considéré qu'il s'agissait d'une question de droit privé et qui échappait à leur compétence. L'accès à la porte d'entrée des recourants n'est effectivement pas supprimé; seul l'escalier y conduisant devra être modifié, puisqu'il n'est actuellement pas possible de l'emprunter sans empiéter sur la parcelle voisine. Cela étant, les critiques des recourants sortent du cadre de l'art. 58 al. 2 LCI. Mal fondé, le présent grief doit être rejeté.
7. Les considérants qui précèdent conduisent au rejet du recours, dans la mesure où il est recevable. Conformément aux art. 66 al. 1 et 68 al. 2 LTF, les frais judiciaires sont mis à la charge des recourants, de même qu'une indemnité de dépens en faveur de l'intimée.

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. Les recourants verseront à l'intimée une indemnité de 2'000 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et au Tribunal administratif du canton de Genève.
Lausanne, le 10 mars 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Féraud Mabillard