Faits:
A. A.a X._ et Y._ sont copropriétaires de la parcelle no 6086 de la commune de D._, d'une superficie de 249 m2. C._ est propriétaire de la parcelle adjacente n° 6085, d'une surface de 403 m2. Les deux parcelles sont issues de la division de la parcelle n° 3171, qui appartenait à E._.
X._ et Y._ font valoir des droits sur une surface de terrain de 3,5 m2, incluse dans la parcelle n° 6085. Cette surface constitue une partie de leur seconde place de parc, située dans le prolongement de la première, et dont ils bénéficient en fait depuis la construction de leur villa en 2001.
A.b En janvier 2000, la société F._ SA, soit pour elle E._, a conclu avec C._ un contrat portant sur l'acquisition de la villa A (contrat conclu le 18 janvier 2000), et avec les époux X. et Y._, un contrat portant sur l'acquisition de la villa B (contrat conclu le 29 janvier 2000). Ce dernier contrat comprenait l'aménagement de deux places de parking extérieures. A chaque contrat était annexé un plan d'aménagement, établi par l'architecte G._. Ce plan d'aménagement, dressé le 9 décembre 1999, prévoyait un décrochement de 3,5 m2 au profit des époux X. et Y._, dans la future limite de propriété de C._. Cette petite surface devait leur permettre l'aménagement des deux places de parc qui leur étaient destinées.
Sur mandat de E._, le géomètre officiel H._ a procédé à la division de la parcelle n° 3171 en quatre nouvelles parcelles, dont les parcelles n° 6085 et 6086. Le plan figurant dans le dossier de mutation parcellaire, daté du 7 juillet 2000, ne prévoyait cependant pas le décrochement de 3,5 m2 initialement prévu dans le plan d'aménagement établi par l'architecte G._. Les deux parcelles n° 6085 et 6086 étaient au contraire délimitées par un tracé rectiligne, de sorte qu'une des places de parking des époux X. et Y._ s'en trouvait réduite.
Par acte notarié du 26 janvier 2001, E._ a procédé à la division de la parcelle n° 3171. Le notaire qui a instrumenté l'acte s'est basé sur le dossier de mutation parcellaire, dont le plan ne prévoyait pas le décrochement de 3,5 m2. Le même jour, par acte de vente notarié, E._ a vendu la parcelle n° 6086 aux époux X. et Y._. Le 21 mars 2001, il a ensuite vendu la parcelle adjacente à C._. Les deux actes de vente notariés font référence à l'existence d'un contrat d'entreprise avec la société F._ SA, portant sur la construction des villas A et B et leurs places de parcs respectives.
Afin de clarifier la portée d'une servitude de passage grevant la propriété de C._, les époux X. et Y._ ont chargé le géomètre H._ de procéder au piquetage de son assiette. A cette occasion, le géomètre a fixé la limite entre les deux propriétés. Le piquetage a alors révélé qu'une partie de la place de parking des époux X. et Y._ se trouvait sur la parcelle voisine de C._, situation dont les époux X. et Y._ ont informé la société F._ SA. Le 25 juin 2003, celle-ci a alors proposé à C._ de modifier les limites des places de parking et de l'indemniser en conséquence. Celle-ci n'a donné aucune suite à la proposition qui lui était adressée. Le 28 septembre 2004, elle a informé ses voisins qu'elle se considérait propriétaire de la surface litigieuse et qu'ils ne devaient pas déplacer les bacs à fleurs ou les poteaux qui s'y trouvaient.
B. Par demande de conciliation du 15 décembre 2005, introduite devant le Tribunal de première instance du canton de Genève le 27 janvier 2006, X._ et Y._ ont ouvert action en revendication et en modification des limites cadastrales à l'encontre de C._.
Par jugement du 31 mai 2007, le Tribunal de première instance de Genève a ordonné à la défenderesse de restituer aux demandeurs la surface de 3,5 m2, autorisé les demandeurs à mandater à leurs frais un géomètre officiel pour modifier les limites du bien-fonds, invité le géomètre à établir de nouveaux plans en prenant en compte le décrochement de 3,5 m2 conformément aux contrats des 18 et 29 janvier 2000 conclus par chacune des parties avec F._ SA, et à procéder à toutes opérations utiles à la modification du registre foncier.
Statuant sur appel de la défenderesse le 24 avril 2008, la Cour de justice genevoise a annulé le jugement de première instance et rejeté l'action des demandeurs.
C. Contre cet arrêt, les demandeurs exercent un recours en matière civile ainsi qu'un recours constitutionnel subsidiaire, prenant les mêmes conclusions dans les deux recours. Les époux X. et Y._ demandent principalement la constatation de leur droit de propriété sur les 3,5 m2 litigieux, la restitution de cette surface et l'autorisation de mandater un géomètre afin de modifier les limites, d'établir de nouveaux plans et de faire procéder aux modifications du registre foncier. Subsidiairement, ils concluent au renvoi de la cause à la cour cantonale.
L'intimée conclut principalement à l'irrecevabilité du recours en matière civile, faute de question juridique de principe, subsidiairement à son rejet. Elle demande également le rejet du recours constitutionnel subsidiaire, tout en se rapportant à justice quant à sa recevabilité.
Par ordonnance du 3 juin 2008, l'octroi de l'effet suspensif a été refusé aux recourants.

Considérant en droit:
1. 1.1 Le litige oppose les parties sur une question relative aux limites de leur propriété privée, dont la valeur est inférieure à 30'000 fr. Le seuil fixé à l'<ref-law> pour la recevabilité du recours en matière civile n'est donc pas atteint. Contrairement à ce que soutiennent les recourants, l'affaire qui les oppose ne soulève pas une question juridique de principe (<ref-law>; sur cette notion, cf. <ref-ruling> consid. 1.2; <ref-ruling> consid. 1, 645 consid. 2.4 et les références citées). La question juridique posée en l'espèce concerne en effet l'application des règles du code civil relatives à l'étendue de la propriété sur les immeubles ainsi qu'à la portée de leur délimitation figurant sur les plans conservés au registre foncier. Réglée par la loi et largement commentée par la doctrine et la jurisprudence, cette question ne peut dès lors être considérée comme une question de principe, de sorte que le recours en matière civile doit être déclaré irrecevable. Il convient néanmoins d'examiner si la voie du recours constitutionnel subsidiaire au sens des <ref-law> est ouverte.
1.2 Le recours a été déposé en temps utile contre une décision finale rendue par une autorité de dernière instance cantonale (art. 75 al. 1, 90, 100 al. 1 et 117 LTF). Les recourants ont en outre pris part à l'instance précédente et démontrent un intérêt juridique à la modification de la décision attaquée (<ref-law>), si bien que le recours constitutionnel est en principe recevable. Seule la violation des droits constitutionnels peut être examinée (<ref-law>).
2. La motivation de la cour cantonale n'est pas particulièrement claire. Elle a admis que le plan n'emportait qu'une présomption d'exactitude et que le propriétaire pouvait, en tout temps, établir son droit de propriété. La dernière instance cantonale a toutefois jugé que le titre d'acquisition des demandeurs - l'acte de vente de la parcelle - n'avait pas d'influence sur le droit réel lui-même. Cet acte portait bien sur la parcelle n° 6086 telle qu'elle résultait de la division de la parcelle no 3171 et pourrait, à cet égard, faire naître une créance à l'égard du vendeur. Il ne pouvait cependant pas conduire à transférer sans autre la propriété sur une part de terrain qui n'était pas comprise dans la délimitation de la parcelle requise. Elle a donc estimé que la question de la bonne foi de l'acquéreur de la parcelle voisine (<ref-law>) ne devait pas être examinée.
Dans leur recours constitutionnel subsidiaire, les recourants soutiennent qu'ils ont démontré l'inexactitude des registres publics, conformément à l'<ref-law>, et que la cour cantonale n'en a pas tenu compte. Elle s'est ainsi référée à un plan - établi par le géomètre et figurant au dossier de mutation parcellaire - dont elle connaissait l'inexactitude et dont elle savait qu'il ne reflétait pas la commune et réelle intention des parties, pour rendre une décision qui, partant, serait insoutenable et heurterait de manière grave le sentiment de la justice et de l'équité. En déniant aux recourants la qualité de propriétaires de la surface litigieuse, la Cour de justice aurait également violé la garantie de la propriété prévue à l'art. 26 al. 1 Cst.
3. 3.1 L'arbitraire prohibé par l'art. 9 Cst. ne résulte pas du seul fait qu'une autre solution pourrait entrer en considération ou même qu'elle serait préférable; le Tribunal fédéral ne s'écarte de la solution retenue en dernière instance cantonale que si elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté ou si elle heurte de manière choquante le sentiment de la justice ou de l'équité. Il ne suffit pas que la motivation de la décision soit insoutenable; encore faut-il qu'elle soit arbitraire dans son résultat (<ref-ruling> consid. 5.1; <ref-ruling> consid. 2.1, 57 consid. 2; <ref-ruling> consid. 3.1).
3.1.1 Le registre foncier donne l'état des droits sur les immeubles (<ref-law>); il comprend le grand livre et les documents complémentaires, en particulier les plans (<ref-law>).
Les immeubles, notamment les biens-fonds, sont immatriculés au registre foncier (art. 943 al. 1 ch. 1. CC). L'immatriculation a pour effet principal de créer une unité foncière, c'est-à-dire un objet de droits réels immobiliers (PAUL-HENRI STEINAUER, Les droits réels, tome I, 4e éd. 2007, n. 653). L'immatriculation d'un immeuble au registre foncier se fait au moyen de son tracé sur le plan, de l'ouverture d'un feuillet au grand livre et de l'établissement de son état descriptif (art. 1 al. 1 de l'Ordonnance du 22 février 1910 sur le registre foncier [ORF; RS 211.432.1]). Le plan est dressé, dans la règle, sur la base d'une mensuration officielle (<ref-law> et 2 al. 1 ORF). Les plans originaux sont conservés à l'office des mensurations cadastrales et un double de ces plans se trouve au registre foncier (<ref-law>). Le feuillet dans le grand livre précise la surface du bien-fonds, renvoie au plan et indique son propriétaire (<ref-law>). En cas de division d'un bien-fonds par parcellement, le conservateur clôt l'ancien feuillet (<ref-law>) et ouvre de nouveaux feuillets en y reportant les droits conformément aux conventions des parties (PAUL-HENRI STEINAUER, op. cit., n. 665 ss).
3.1.2 Le plan représente donc géométriquement l'immeuble, en indiquant notamment sa situation et ses limites (art. 7 al. 1 de l'Ordonnance du 18 novembre 1992 sur la mensuration officielle [OMO; RS 211.432.2]). Une fois mis en vigueur par l'autorité compétente, le plan est un titre public au sens de l'<ref-law> et son exactitude est présumée (arrêt du Tribunal fédéral 6S.276/2004 consid. 3.1, in RNRF 2006 p. 215; PAUL-HENRI STEINAUER, op. cit., n. 569).
En relation avec cette individualisation géométrique du bien-fonds par le plan, l'<ref-law> définit l'étendue horizontale du droit de propriété sur le bien-fonds. Selon l'<ref-law>, les limites des immeubles sont déterminées par le plan et par la démarcation sur le terrain. Par démarcation sur le terrain, il y a lieu de comprendre les signes officiels qui rendent visibles les limites (HEINZ REY, in Basler Kommentar, Zivigesetzbuch II, 3e éd. 2007, n. 3 ad art. 668; ARTHUR MEIER-HAYOZ, Berner Kommentar, 3e éd. 1974, n. 6 sv. ad art. 668). S'il y a contradiction entre la démarcation sur le terrain et les limites figurant sur le plan, l'<ref-law> présume que c'est le plan qui est exact. Aussi bien pour le plan que pour la démarcation sur le terrain, l'<ref-law> n'institue toutefois qu'une présomption d'exactitude; le propriétaire peut donc établir que son droit de propriété s'étend au-delà de la limite marquée sur le terrain et/ou sur le plan. En revanche, que les limites figurant sur le plan correspondent ou non à celles marquées sur le terrain, l'exactitude du plan, qui est partie constitutive du registre foncier (<ref-law>), est élevée au rang de fiction à l'égard de l'acquéreur de bonne foi du fonds (<ref-law>; arrêt du Tribunal fédéral 5C.12/1999 du 11 février 1999, consid. 2 et 3, in Rep. 1999 p. 61; PAUL-HENRI STEINAUER, Les droits réels, tome 2, 3e éd. 2002, n. 1604 sv.).
3.2 Selon la cour cantonale, l'acte de vente notarié que les recourants ont passé le 26 janvier 2001 portait sur la parcelle n° 6086 telle qu'elle résultait de la division de la parcelle n° 3171, instrumentée le même jour. Le titre d'acquisition précité ne pouvait certainement pas conduire à transférer sans autre la propriété sur une part de terrain qui n'était pas comprise dans la délimitation de la parcelle acquise, telle qu'elle était immatriculée au registre foncier. La référence, dans le corps de l'acte de vente notarié, à un contrat d'entreprise en vue de l'édification d'une villa, ne permettait pas de modifier la portée de cet acte quant à l'étendue de la parcelle vendue.
3.3 La subsomption effectuée par la cour cantonale n'est pas arbitraire. La parcelle n° 6086, d'une surface de 249 m2, est issue de la division de l'ancienne parcelle n° 3171. Elle a été créée par l'acte de division parcellaire, daté du 26 janvier 2001 et instrumenté par le notaire mandaté par le propriétaire de la parcelle divisée. L'instrumentation de cette opération a été effectuée sur la base du dossier de mutation, dans lequel figurait le plan dressé par le géomètre officiel le 7 juillet 2000, plan qui faisait état d'une limite rectiligne entre la parcelle des recourants et celle de l'intimée. La délimitation de la parcelle était donc claire au vu du plan du registre foncier, celui-ci correspondant à l'acte de division ainsi qu'au dossier de mutation. Il ne souffrait donc d'aucune inexactitude. Les recourants ont acquis en copropriété cette parcelle n° 6086 par acte de vente du 26 janvier 2001. Ils sont donc devenus propriétaires de la surface telle qu'elle était délimitée au plan figurant au registre foncier.
Dans la mesure où les recourants se prévalent des pourparlers qui ont précédé l'acte de vente notarié, de leur erreur au moment de la signature de cet acte et de l'erreur du vendeur au moment de la signature de l'acte de division parcellaire, ils font en réalité valoir des droits personnels à l'attribution de la surface litigieuse, sans pourtant établir de droit réel de propriété sur celle-ci. Le plan ne bénéficie certes que d'une présomption d'exactitude selon l'<ref-law>. Mais, s'il correspond à l'acte constitutif - ici à l'acte de division parcellaire - et donc aux pièces justificatives du registre foncier, il est exact. Les recourants ne peuvent ainsi rien déduire, sur le plan des droits réels, d'une intention du propriétaire qui n'a pas trouvé expression dans l'acte de division parcellaire et dans le plan conservé au registre foncier. Leur grief doit ainsi être rejeté.
4. Les recourants soutiennent ensuite que la Cour de justice a violé la garantie de propriété telle qu'elle est prévue par l'art. 26 Cst.
Ce grief n'a pas de portée propre dans la mesure où les droits de propriété sont réglés de manière exhaustive par le Code civil et où il a été établi que les recourants ne sont pas propriétaires de la surface litigieuse.
5. Au vu de ce qui précède, le recours en matière civile doit être déclaré irrecevable et le recours constitutionnel subsidiaire doit être rejeté, dans la mesure de sa recevabilité. Les frais judiciaires (<ref-law>) et les dépens (art. 68 al. 1 et 2 LTF) sont mis à la charge des recourants qui succombent.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière civile est irrecevable.
2. Le recours constitutionnel subsidiaire est rejeté dans la mesure où il est recevable.
3. Les frais judiciaires, arrêtés à 2'000 fr, sont mis solidairement à la charge des recourants.
4. Une indemnité de 2'000 fr., à payer à l'intimée à titre de dépens, est mise solidairement à la charge des recourants.
5. Le présent arrêt est communiqué aux parties et à la Chambre civile de la Cour de justice du canton de Genève.
Lausanne, le 27 octobre 2008
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président: La Greffière:
Raselli de Poret