Faits:
A. La parcelle n° 404 de la commune de A._ appartient depuis 1929 à la Société Y._.
Les époux X._ sont copropriétaires de la parcelle voisine n° 682 depuis le 26 février 2003. Une villa y est érigée.
B. B.a En 1931, les parcelles étaient configurées de manière différente et un chemin vicinal traversait certaines d'entre elles. A cette époque, un droit de passage grevant plusieurs fonds, dont celui portant aujourd'hui le n° 404, a été inscrit au registre foncier sous référence xxxx au profit de l'actuelle parcelle n° 682. L'acte constitutif de cette servitude mentionnait que « le droit de passage ne pourra être exercé que sur les parties desdites parcelles formant actuellement le chemin. »
En 1951, ce chemin (actuellement chemin B._) est devenu une parcelle distincte et dépendante des parcelles riveraines et a été immatriculé au registre foncier sous n° 629.
B.b Jusqu'en avril 2008, les époux X._, comme les précédents propriétaires, accédaient à leur terrain en empruntant un chemin privatif aménagé au début des années 1940 et traversant d'est en ouest la parcelle contiguë n° 404. Le terrain étant légèrement en pente à cet endroit, l'aménagement de ce chemin a nécessité l'élévation d'une petite bordure haute de 50 cm, longue de 8 mètres environ et large de 20 cm. De l'autre côté du chemin, en contrebas, un mur de soutènement de moins de 1 mètre de hauteur a été édifié pour retenir la terre et les éboulements.
Les époux X._ disposent d'un autre accès à leur propriété, par son côté nord en suivant le chemin B._ qui contourne la parcelle n° 404. Cette voie permet le passage des véhicules à moteur.
C. Depuis 2003, un litige oppose les époux X._ et la Société Y._ au sujet du chemin privatif que les premiers utilisent pour accéder à leur parcelle.
Dans le cadre d'une action négatoire ouverte par les époux X._ contre la Société Y._, le Tribunal de première instance de Genève a, le 27 septembre 2007, rejeté la conclusion des époux tendant à ce qu'il soit constaté que la parcelle n° 404 est grevée d'une servitude foncière de passage au profit de la parcelle n° 682 s'exerçant sur le chemin traversant perpendiculairement (soit d'est en ouest) la parcelle n° 404. Il a également rejeté la demande reconventionnelle de la Société Y._ qui tendait à la constatation que les époux X._ n'étaient pas au bénéfice d'un droit de passage de nature réelle sur la parcelle n° 404. En bref, cette autorité a considéré que l'assiette de la servitude de passage ne correspondait pas au chemin qui traversait d'est en ouest la parcelle n° 404 mais au tracé de l'actuel chemin B._. Ce jugement est définitif et exécutoire.
D. Après avoir averti les époux X._ que le passage traversant la parcelle n° 404 d'est en ouest allait être renaturalisé, la Société Y._ a entrepris, le 2 avril 2008, des travaux consistant à enlever le pavement de ce chemin et à y planter un arbre, empêchant ainsi l'accès à la parcelle n° 682 par cette voie.
Les époux X._ ont ouvert contre la Société Y._ une requête de mesures provisionnelles urgentes tendant à ce qu'il soit fait interdiction de modifier, détruire ou renaturaliser le passage en question, à ce qu'il lui soit ordonné de le remettre en état afin qu'ils puissent à nouveau accéder à la voie publique, ces mesures devant être prononcées sous la menace des sanctions prévues à l'art. 292 CP.
Par ordonnance du 13 mai 2008, le Tribunal de première instance a rejeté cette requête.
La Cour de justice du canton de Genève a, le 25 septembre 2008, rejeté le recours formé par les époux X._ contre cette ordonnance.
E. Par mémoire du 31 octobre 2008, les époux X._ interjettent un recours en matière civile auprès du Tribunal fédéral. A titre principal, ils reprennent les conclusions formulées en première instance. A titre « alternatif », ils demandent l'annulation de l'arrêt attaqué et le renvoi de la cause à l'autorité précédente pour nouvelle décision.
Des observations n'ont pas été requises.

Considérant en droit:
1. 1.1 L'arrêt attaqué a été rendu en matière civile au sens de l'art. 72 al. 1 LTF. Il porte sur l'octroi de mesures provisionnelles au sens des art. 320 ss de la procédure civile genevoise en matière de mesures provisionnelles (art. 320 ss LPC/GE; RS E 3 05), lesquelles doivent être validées dans un certain délai par l'introduction d'une action sur le fond (art. 330 LPC/GE; Bertossa/Gaillard/Guyet/Schmidt, Commentaire de la loi de procédure civile genevoise, n. 11 ad art. 321 LPC/GE) et ne valent que pour la durée de cette procédure. La décision sur une telle requête constitue une décision incidente au sens de l'art. 93 LTF. En l'espèce, elle cause un préjudice irréparable, de sorte que le recours au Tribunal est ouvert sous l'angle de l'art. 93 al. 1 let. a LTF. La Cour de justice a en outre statué comme autorité de dernière instance (art. 75 al. 1 LTF) dans une affaire pécuniaire dont la valeur litigieuse est supérieure à 30'000 fr. (art. 74 al. 1 let. b LTF).
1.2 Le recours étant dirigé contre une décision portant sur des mesures provisionnelles au sens de l'art. 98 LTF, seule peut être invoquée la violation de droits constitutionnels.
Le Tribunal fédéral n'examine la violation de droits fondamentaux ainsi que celle de dispositions de droit cantonal et intercantonal que si ce grief est invoqué et motivé par le recourant (art. 106 al. 2 LTF), c'est-à-dire que s'il a été expressément soulevé et exposé de façon claire et détaillée (<ref-ruling> consid. 6, 638 consid. 2). Le recours doit, comme sous l'empire de l'art. 90 al. 1 let. b OJ, satisfaire au principe d'allégation (Rügeprinzip): il doit indiquer quelle disposition constitutionnelle ou légale a été violée et démontrer de façon précise en quoi consiste la violation (<ref-ruling> consid. 3.2 et les arrêts cités).
2. L'autorité cantonale a examiné les trois fondements juridiques énoncés par les recourants pour rendre vraisemblable leur droit à l'utilisation du chemin litigieux traversant la parcelle voisine. En premier lieu, elle a considéré que les recourants n'avaient pas rendu vraisemblable le transfert d'assiette de la servitude inscrite sous xxxx sur le chemin traversant d'est en ouest la parcelle n° 404. Elle s'est référée au jugement définitif rendu par le Tribunal de première instance le 27 septembre 2007, qui avait estimé que le droit de passage inscrit sous cette référence correspondait au tracé de l'actuel chemin B._; selon la Cour de justice, les documents produits par les recourants ne conduisaient pas à modifier cette appréciation. L'autorité précédente a encore rejeté la conclusion des recourants tendant à la constitution à titre provisionnel, d'une servitude d'empiètement en leur faveur (art. 674 CC). Ceux-ci prétendaient que le chemin traversant la parcelle de l'intimée faisait partie intégrante de leur villa et qu'ils pouvaient ainsi être mis au bénéfice d'une servitude d'empiètement. L'autorité cantonale a considéré que le chemin et sa bordure ne pouvaient être qualifiés d'ouvrage au sens de l'art. 674 CC et qu'ils ne faisaient nullement partie intégrante des constructions qui se trouvent sur la parcelle des recourants. Enfin, la Cour cantonale a rejeté la requête qui tendait à la constitution, à titre provisionnel, d'un droit de passage nécessaire au sens de l'art. 694 CC en faveur des recourants. A ce sujet, elle a estimé que le passage demandé n'était pas nécessaire puisque les recourants pouvaient accéder à leur parcelle - même au moyen de véhicules à moteur - par le côté nord de celle-ci en empruntant le chemin B._ et qu'ils n'avaient ainsi rendu vraisemblable ni l'urgence, ni l'apparence du droit invoqué.
3. Les recourants soutiennent que l'autorité cantonale a constaté les faits de manière arbitraire (art. 9 Cst.).
3.1 S'agissant de l'appréciation des preuves et la constatation des faits, le Tribunal fédéral se montre réservé, vu le large pouvoir qu'il reconnaît en la matière aux autorités cantonales (<ref-ruling> consid. 4b; <ref-ruling> consid. 9 et les arrêts cités). Il n'intervient, du chef de l'art. 9 Cst., que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, a omis sans motifs objectifs de tenir compte de preuves pertinentes ou a opéré, sur la base des éléments recueillis, des déductions insoutenables (<ref-ruling> consid. 2.1; <ref-ruling> consid. 2.1); encore faut-il que la correction du vice soit susceptible d'influer sur le sort de la cause (art. 97 al. 1 in fine LTF).
3.2 Selon les recourants, il existe le long du chemin traversant la parcelle n° 404 un mur de soutènement d'une longueur de 15,75 mètres sur 0,75 mètre de large dans sa partie visible; dans sa partie enterrée, ce mur se poursuit jusque sur leur terrain. Ce fait ressortirait du plan qu'ils ont versé en cause, dessiné par l'architecte C._. La Cour cantonale a fait état de cette construction sans toutefois décrire les dimensions exactes de celle-ci. Sur la base de la configuration telle qu'elle aurait dû être constatée, les recourants sont d'avis que la cour cantonale aurait considéré ce chemin comme un ouvrage et les aurait ainsi mis au bénéfice d'une servitude d'empiètement à charge de la parcelle voisine.
Comme les recourants le relèvent eux-mêmes, sur le plan auquel ils se réfèrent, on ne distingue nullement de partie enterrée se prolongeant sur leur terrain. Sous cet angle, on ne peut donc reprocher à l'autorité cantonale d'avoir mal interprété ce moyen de preuve et d'avoir ainsi procédé à une constatation arbitraire des faits. Quant aux dimensions du mur décrit par la Cour de justice, le seul fait de tenir compte d'une taille supérieure n'aurait aucune influence sur leur prétention en constitution d'une servitude d'empiètement. Il n'y a donc pas lieu de s'écarter des faits retenus sur ce point.
3.3 Les recourants prétendent que l'autorité cantonale n'a reproduit que de manière incomplète, dans sa partie « En faits », le jugement rendu par le Tribunal de première instance le 27 septembre 2007. Selon eux, la Cour de justice aurait dû mentionner le passage suivant : « Il ressort en outre de la procédure que dans le cadre de l'introduction du Registre Fédéral à A._, la parcelle n° 629 créée en 1952 et correspondant au tracé du chemin B._, a été dégrevée de cette servitude le 27 mars 2007. »
Le grief doit être rejeté dès lors que ce fait est repris dans le jugement attaqué. Celui-ci mentionne à la let. B.f que la servitude de passage grevant la parcelle n° 629 constituée par le chemin B._ a été radiée par le registre foncier en mars 2007.
3.4 La Cour de justice aurait encore versé dans l'arbitraire en constatant que, dans le jugement du 27 septembre 2007, le Tribunal de première instance aurait jugé que les recourants avaient perdu leur droit de passage sur la parcelle n° 404. Une nouvelle fois, ce reproche procède d'une mauvaise lecture de l'arrêt cantonal. En effet, sous let. B.e, l'autorité précédente explique que, dans le cadre d'une action négatoire ouverte par les recourants contre l'intimée, celle-ci avait conclu à titre reconventionnel à ce qu'il soit constaté que les recourants ne sont pas au bénéfice d'un droit de passage de nature réelle sur la parcelle n° 404. La cour cantonale fait état ensuite du rejet par le Tribunal de première instance de cette demande reconventionnelle, celui-ci ayant retenu que les recourants disposaient d'un droit de passage dont l'assiette s'étendait sur l'actuel chemin B._ et non sur le tracé allégué par les recourants. Contrairement à ce qu'ils soutiennent, l'autorité précédente n'a donc nullement retenu qu'aux termes du jugement rendu le 27 septembre 2007 par le Tribunal de première instance, ils n'avaient plus de droit de passage.
4. Les recourants estiment qu'en jugeant qu'ils n'avaient pas rendu vraisemblable leur droit à la constitution d'une servitude d'empiètement en leur faveur, la cour cantonale a violé la garantie de la propriété (art. 26 Cst.).
4.1 La garantie constitutionnelle de la propriété ne peut être invoquée directement dans un litige entre personnes privées (cf. <ref-ruling> consid. 5; <ref-ruling> consid. 3a). Les particuliers sont protégés par les lois civiles et pénales des atteintes que d'autres sujets de droit privé pourraient porter à leurs droits constitutionnels. Ils ne peuvent prétendre que le jugement attaqué viole directement la garantie de la propriété, ce jugement étant rendu en application d'une loi fédérale dont le Tribunal fédéral ne peut revoir la constitutionnalité (art. 191 Cst; ATF <ref-ruling> consid. 3a).
4.2 La garantie de la propriété peut en revanche être invoquée directement lorsque le recours est dirigé contre une décision de mesures provisionnelles fondée comme en l'espèce sur le droit de procédure cantonal (ATF <ref-ruling> consid. 3.2). Le recourant peut alors se plaindre de ce que le droit cantonal en soi ou tel qu'appliqué par l'autorité cantonale, viole la garantie de la propriété, ce que le Tribunal fédéral examine librement (<ref-ruling> consid. 2b).
4.3 En l'occurrence, seul entrerait donc en ligne de compte une violation de l'art. 26 Cst. par le droit cantonal ou par l'application de ce droit. Les recourants ne soutiennent pas que les dispositions cantonales relatives aux mesures provisionnelles (cf. art. 320 ss LPC/GE) ou leur application seraient inconstitutionnelles. Ils décrivent les conditions prévues par l'art. 674 CC pour l'octroi d'une servitude d'empiètement et affirment qu'elles sont remplies en l'espèce. Un tel développement tend à démontrer une violation du droit fédéral. L'autorité cantonale a rejeté la requête au motif qu'une des conditions au prononcé des mesures provisionnelles n'était pas remplie (sur les conditions du prononcé de telles mesures, cf. <ref-ruling> consid. 3a), soit en l'espèce que les recourants n'avaient pas rendu vraisemblable le bien-fondé de leur prétention matérielle. Les recourants ne développent aucun argument sur l'interprétation de cette condition. Dans ces conditions, la motivation du grief ne répond pas aux exigences posées par l'art. 106 al. 2 LTF.
5. Les recourants se plaignent encore d'une atteinte à la garantie de la propriété au motif que la cour cantonale n'a pas admis la vraisemblance d'un transfert d'assiette de la servitude. S'agissant à nouveau d'un grief tiré de la violation directe de la garantie constitutionnelle de la propriété invoquée dans un litige entre particuliers, les recourants ne peuvent se plaindre que de ce que le droit cantonal en soi ou tel qu'appliqué viole l'art. 26 Cst. (cf. consid. 4.1-4.3 supra). Or, ils n'expliquent pas en quoi l'autorité précédente, qui a rejeté la requête parce que les recourants n'avaient pas rendu vraisemblable le bien-fondé de leur prétention matérielle, aurait interprété cette notion de droit cantonal d'une manière contraire à la garantie de la propriété. Le grief est par conséquent irrecevable, faute de motivation suffisante (art. 106 al. 2 LTF).
6. Selon les recourants, le refus à titre provisionnel de l'octroi d'un passage nécessaire au sens de l'art. 694 CC viole la garantie de la propriété.
A l'appui de ce grief, ils affirment que l'utilisation du passage pendant 68 ans suffit pour en faire un droit acquis, protégé par l'art. 26 Cst. et qu'en conséquence, il appartenait à l'intimée d'établir qu'ils n'avaient pas de droit de passage. Les recourants prétendent ensuite que, contrairement à ce qui a été retenu par la cour cantonale, leur requête répond à un besoin urgent car sans ce passage, ils seraient contraints d'utiliser le passage au nord, très difficile d'accès. Ils citent ensuite un extrait d'un avis de droit du professeur Steinauer lequel procède à une pesée des intérêts des parties. Cette argumentation est impropre à démontrer que l'interprétation des règles de droit cantonal relatives au prononcé de mesures provisionnelles viole la garantie de la propriété. La cour cantonale a rejeté la requête au motif que les recourants n'avaient rendu vraisemblable ni l'urgence ni l'apparence du droit invoqué. Or, les recourants ne disent à aucun moment dans quelle mesure l'interprétation des conditions de l'urgence et de la vraisemblance du droit invoqué (cf. consid. 2 supra) est contraire à l'art. 26 Cst. Il n'y a donc pas lieu d'examiner ce grief au fond (art. 106 al. 2 LTF).
7. En conséquence, le recours doit être rejeté dans la faible mesure de sa recevabilité. Les recourants, qui succombent, supporteront solidairement les frais judiciaires (art. 66 al. 1 et 5 LTF). Il n'y a pas lieu d'allouer de dépens à l'intimée, qui n'a pas été invitée à se déterminer (art. 68 al. 1 LTF).

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 à 8'000 fr., sont mis solidairement à la charge des recourants.
3. Le présent arrêt est communiqué aux parties et à la 1ère Section de la Cour de justice du canton de Genève.
Lausanne, le 27 avril 2009
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl Rey-Mermet