Faits:
A. Par jugement du 17 janvier 2008, le Tribunal de première instance du canton de Genève a rejeté l'action en annulation de mariage déposée par X._, né le 24 septembre 1949, de nationalité française, contre dame X._, née le 14 juillet 1975, de nationalité algérienne.
B. Le mandataire de X._ a reçu le jugement du Tribunal de première instance le 24 janvier 2008. Agissant pour le compte de son client, il a appelé de ce jugement par acte expédié le 26 février 2008 et télécopie dudit acte transmise à la Cour de justice le 25 février 2008 à 21h11. Par arrêt du 17 mars 2008, cette dernière autorité a déclaré l'appel irrecevable.
C. X._ interjette un recours constitutionnel subsidiaire et un recours en matière civile contre cet arrêt, concluant à son annulation ainsi qu'au renvoi de la cause à l'instance cantonale pour nouvelle décision sur l'appel.
Appelée à se déterminer, dame X._ conclut au rejet du recours.
La Cour de justice propose quant à elle l'admission du recours, admettant qu'elle avait commis une inadvertance dans l'appréciation du moyen de preuve avancé par le recourant.

Considérant en droit:
1. Le recourant exerce, dans le même mémoire, un recours constitutionnel subsidiaire - se référant à la voie de droit indiquée par l'arrêt attaqué et considérant la valeur litigieuse inférieure à 30'000 fr - ainsi qu'un recours en matière civile - dans l'éventualité où le Tribunal de céans devait considérer que seule cette voie de droit était ouverte.
La décision querellée est une décision d'irrecevabilité d'un appel dans une cause d'annulation de mariage. Il s'agit ainsi d'une décision finale, rendue en dernière instance cantonale par le tribunal supérieur du canton de Genève, dans une cause de nature non pécuniaire (art. 72 al. 1 et 75 al. 1 et 90 LTF). Le recours a été interjeté en temps utile (art. 46 al. 1 let a et 100 al. 1 LTF) par la partie qui a succombé dans ses conclusions devant l'autorité précédente et démontre un intérêt juridique à l'annulation de la décision attaquée (art. 76 al. 1 LTF). Le recours en matière civile est donc en principe recevable. La voie du recours constitutionnel subsidiaire n'est donc pas ouverte.
2. La Cour de justice a déclaré l'appel irrecevable, considérant qu'en vertu de l'art. 296 LPC/GE (loi de procédure civile genevoise), l'appel devait être interjeté dans un délai de 30 jours dès notification, et, qu'en raison de l'absence de signature valable, un acte transmis par télécopie n'était pas recevable. Dans sa détermination du 18 août 2008, l'autorité cantonale a néanmoins reconnu ne pas avoir tenu compte de la mention figurant sur l'enveloppe ayant contenu l'acte d'appel et a dès lors proposé l'admission du recours.
Le recourant admet que son acte transmis par télécopie n'est pas recevable. Il soutient néanmoins qu'il a déposé l'original signé dans la boîte aux lettres du bureau de poste de Morges le dernier jour du délai, à savoir le 25 janvier 2008 à 22h19. Son conseil avait en effet chargé Me A._ d'expédier l'acte d'appel et, par mention signée figurant au dos de l'enveloppe, Me B._, qui accompagnait le confrère mandaté, a attesté que celui-ci avait bien déposé le pli à l'heure et à la date susmentionnées. Citant l'art. 9 Cst., les art. 1 et 3 de la CEDH, ainsi que l'art. 31 al. 1 LPC/GE, le recourant reproche à la cour cantonale d'avoir fait preuve d'arbitraire dans l'appréciation des faits et des moyens de preuve ainsi que d'avoir violé les dispositions de droit fédéral et de droit cantonal concernant la computation et le respect des délais.
L'intimée soutient que la preuve de l'envoi exigeait la présence de deux témoins.
3. 3.1 La partie qui doit accomplir un acte de procédure doit démontrer qu'elle l'a entrepris à temps. L'expéditeur doit ainsi prouver que son envoi a été expédié le dernier jour du délai à minuit au plus tard (<ref-ruling> consid. 3), peu importe que l'acte ait été remis au guichet de la poste ou déposé dans une boîte aux lettres (<ref-ruling> consid. 3a). Dans l'un et l'autre cas, la date de la remise ou du dépôt est présumée coïncider avec celle du sceau postal. La partie qui prétend avoir déposé son acte la veille de la date attestée par le sceau postal a cependant le droit de renverser cette présomption par tous moyens de preuve appropriés (<ref-ruling> consid. 3a; <ref-ruling> consid. 3b), l'autorité cantonale étant tenue de lui en donner l'occasion (Arrêt 1P.446/2004 du 28 septembre 2004, consid. 2). Le droit de faire administrer ces preuves suppose néanmoins que la demande soit présentée selon les formes et délais prescrits par le droit cantonal (<ref-ruling> consid. 5b/bb; <ref-ruling> 4b). La jurisprudence précise toutefois que l'avocat qui se contente de déposer son pli dans une boîte aux lettres n'est pas sans ignorer le risque qu'il court que ce pli ne soit pas enregistré le jour même de son dépôt, mais à une date ultérieure. S'il souhaite renverser la présomption résultant du sceau postal apposé sur l'enveloppe ayant contenu une pièce de procédure, on est en droit d'attendre de lui qu'il indique spontanément à l'autorité compétente avoir respecté le délai, en présentant les moyens de preuves en attestant (Arrêt 5P.113/2005 consid. 3.1).
3.2 En l'occurrence, le recourant invoque que l'avocat mandaté par son conseil s'est fait accompagner jusqu'à la boîte aux lettres par un confrère, lequel a attesté de la date et de l'heure du dépôt.
Au vu de l'enveloppe originale, agrafée au mémoire d'appel se trouvant dans le dossier cantonal, il est manifeste que la mention indiquée par le recourant y figure. Contrairement à ce qu'avance l'intimée, il n'est pas nécessaire qu'une telle mention soit également apposée dans la télécopie, mais il suffit qu'elle soit inscrite sur l'enveloppe contenant l'acte original. La présence d'un seul témoin doit être considérée comme suffisante, d'autant plus que, constatant la fermeture du bureau de poste, l'expéditeur mandaté a pris la peine de transmettre par téléfax une copie de l'acte d'appel à la Cour de justice. Les raisons pour lesquelles le pli a été déposé dans ces circonstances pourront être examinées par la cour cantonale si besoin est.
4. Le recours doit être admis, l'autorité cantonale ayant, suite à une inadvertance manifeste, omis de constater un fait décisif pour apprécier le respect du délai (art. 105 al. 2 LTF). La cause est par conséquent renvoyée à cette dernière autorité pour nouvelle instruction et décision, cas échéant après instruction sur les circonstances liées au respect du délai. Les frais et dépens sont mis à la charge de l'intimée qui s'est opposée au recours (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours constitutionnel subsidiaire est irrecevable.
2. Le recours en matière civile est admis, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour nouvelle instruction et nouvelle décision.
3. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge de l'intimée.
4. Une indemnité de 2'000 fr., à verser au recourant à titre de dépens, est mise à la charge de l'intimée.
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 16 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