Faits:
A. A.a B._, ressortissante grecque, et A._, d'origine grecque également, se sont mariés le 18 mars 2011 à V._, en Grèce.
L'épouse a séjourné en Suisse du 19 juillet 2010 au 4 janvier 2011 et travaillé durant cette période en tant que médecin interne de D._. Enceinte, elle est retournée en Grèce où elle a repris son activité auprès de E._.
A.b Le 20 juillet 2011, B._ a donné naissance à C._, à New-York où elle s'est rendue le 10 juin 2011 après un séjour de trois semaines auprès de sa s?ur à Genève.
Le 31 août 2011, la mère et l'enfant sont retournées à Genève alors que A._, qui s'était rendu à New-York le 21 juillet 2011, était rentré seul en Grèce le 22 août 2011.
A.c Depuis le 1er novembre 2011, B._ est employée pour une durée indéterminée par F._; elle est inscrite avec son enfant au Service du contrôle des habitants de Lausanne depuis cette même date. La mère et l'enfant sont en outre titulaires d'une autorisation de séjour (permis B) depuis respectivement le 28 novembre 2011 et le 2 mars 2012.
A.d En date du 4 novembre 2011, A._ a saisi le Ministère grec de la justice d'une plainte pour déplacement et non-retour illicite de l'enfant, laquelle a été transmise à l'Office fédéral de la justice (OFJ).
L'OFJ a rejeté la requête par décision du 2 décembre 2011 pour le motif que l'enfant n'avait jamais eu de résidence habituelle en Grèce.
A.e Le 16 décembre 2011, B._ a ouvert une procédure de mesures protectrices de l'union conjugale devant le Président du Tribunal civil de l'arrondissement de Lausanne. La garde sur sa fille lui a été attribuée, à titre superprovisionnel, par ordonnance du 25 janvier 2012.
A.f A._ a quant à lui déposé une demande en divorce auprès du Tribunal collégial de première instance d'Athènes le 28 décembre 2011. Il a obtenu un droit de visite sur C._ au domicile de la mère situé, selon les indications de la requête, en Grèce par ordre provisoire du 21 février 2012.
A.g Depuis le mois de septembre 2011, A._ est venu à plusieurs reprises en Suisse pour voir l'enfant. Il est en outre en contact régulier avec celle-ci et son épouse par le biais de Skype.
B. B.a Par requête du 20 mars 2012 adressée à la Chambre des tutelles du Tribunal cantonal du canton de Vaud, A._ a conclu à ce que le retour de l'enfant C._ soit immédiatement ordonné à son domicile et à ce qu'ordre soit donné à la mère, sous la menace de la peine d'amende prévue à l'<ref-law>, de remettre immédiatement l'enfant au Service de protection de la jeunesse (ci-après: SPJ) afin que celui-ci se charge de la lui remettre, respectivement se charge du rapatriement de l'enfant auprès de lui en Grèce, l'exécution pouvant intervenir, si nécessaire, avec le concours de la force publique.
B.b Le 21 mars 2012, la Chambre des tutelles du Tribunal cantonal du canton de Vaud a désigné Me Catherine Jaccottet Tissot, avocate à Lausanne, en qualité de curatrice de l'enfant pour la procédure de retour.
B.c Par arrêt du 3 mai 2012, la Chambre des tutelles du Tribunal cantonal du canton de Vaud a rejeté la requête en retour formée par A._.
C. Le 14 mai 2012, A._ exerce un recours en matière civile au Tribunal fédéral contre cet arrêt, concluant à sa réforme en ce sens que la requête en retour déposée est admise. Subsidiairement, il conclut à son annulation et au renvoi de la cause pour nouvelle décision. À l'appui de ses conclusions, il se plaint d'arbitraire dans l'établissement des faits ainsi que dans le résultat auquel est parvenue l'autorité inférieure. Il invoque également une violation des art. 13 et 36 Cst. ainsi que 8 CEDH.
Invitées à se déterminer sur le recours, la mère et la curatrice de l'enfant concluent à son rejet; la curatrice sollicite en outre l'octroi de l'assistance judiciaire. La cour cantonale se réfère aux considérants de son arrêt.

Considérant en droit:
1. Le Tribunal fédéral examine d'office la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 et les références citées).
1.1 Les décisions statuant sur le retour d'un enfant en application de la Convention de La Haye sur les aspects civils de l'enlèvement international d'enfants du 25 octobre 1980 (RS 0.211.230.02; CLaH80) ne sont pas des affaires civiles. Il s'agit d'entraide administrative entre les États contractants (<ref-ruling> consid. 2b), donc d'une question relevant du droit public mais qui est en rapport direct avec le respect et la mise en oeuvre du droit civil étranger (art. 72 al. 2 let. b ch. 1 LTF; <ref-ruling>). La Chambre des tutelles du Tribunal cantonal du canton de Vaud a statué en instance cantonale unique conformément à l'art. 7 al. 1 de la loi fédérale sur l'enlèvement international d'enfants et les Conventions de La Haye sur la protection des enfants et des adultes du 21 décembre 2007 (LF-EEA, RS 211.222.32); il y a ainsi exception légale au principe du double degré de juridictions cantonales (<ref-law>). Le délai légal de 10 jours (art. 100 al. 2 let. c LTF) est en outre respecté de sorte que le recours en matière civile est en principe recevable.
1.2 Le recours en matière civile peut être formé pour violation du droit fédéral et du droit international (art. 95 let a et b LTF). Le Tribunal fédéral applique le droit d'office (<ref-law>) sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut donc admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 2.2). Il ne connaît cependant de la violation des droits fondamentaux ou du droit cantonal que si ce grief a été soulevé et motivé (<ref-law>; <ref-ruling> consid. 3.2; <ref-ruling> consid. 1.4.2). Si le recourant se plaint de la violation de tels droits, il doit ainsi satisfaire au principe d'allégation (Rügeprinzip, principio dell'allegazione), en indiquant précisément quelle disposition constitutionnelle ou légale a été violée et en démontrant, par une argumentation précise, en quoi consiste la violation (<ref-ruling> consid. 1.4; <ref-ruling> consid. 1.4.2).
1.3 Saisi d'un recours en matière civile, le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ces faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>), et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>). Le recourant qui entend invoquer que les faits ont été établis de manière manifestement inexacte (<ref-law>), c'est-à-dire que les constatations de fait sont arbitraires au sens de l'art. 9 Cst. (ATF <ref-ruling> consid. 1.2.2), doit satisfaire au principe d'allégation susmentionné (cf. supra consid. 1.2).
1.4 Les faits et moyens de preuve nouveaux sont prohibés, à moins de résulter de la décision de l'autorité précédente (<ref-law>). Cela vaut également pour les faux faits et preuves nouveaux que le recourant a omis de présenter dans la procédure cantonale et qui n'ont donc pas pu être pris en considération (<ref-ruling> consid. 4.4.3). Il n'y a exception à cette règle que lorsque c'est la décision de l'autorité précédente qui, pour la première fois, a rendu pertinents ces faits ou moyens de preuve, ce qu'il appartient au recourant de démontrer (<ref-ruling> consid. 3).
En l'espèce, la seule indication que certaines pièces produites, en particulier les courriels, n'auraient été retrouvées qu'après l'audience devant l'instance précédente ne saurait suffire à démontrer que ceux-ci résulteraient de la décision de l'autorité précédente, ce d'autant plus que le recourant a prétendu, dès le dépôt de sa requête, que l'intimée s'était rendue à New-York sans son accord et qu'elle avait caché le nom du père de l'enfant aux autorités américaines. Il s'ensuit que les faits et moyens de preuve invoqués pour la première fois devant le Tribunal fédéral sont irrecevables.
2. En substance, la cour cantonale a considéré que C._, n'avait pas pu avoir, en tant que nasciturus, de résidence habituelle en Grèce mais avait eu sa première résidence habituelle en Suisse, de sorte qu'elle ne saurait y avoir été déplacée illicitement depuis la Grèce. Elle a également nié un éventuel abus de droit de la part de la mère, en tant qu'elle avait choisi d'accoucher à New-York plutôt qu'en Grèce, puisqu'il s'agissait d'un choix commun des parties.
3. Dans un premier grief, le recourant se plaint d'arbitraire dans la constatation des faits et prétend que l'intimée aurait commis un abus de droit, en tant qu'elle aurait décidé de son seul chef de quitter la Grèce pour, après un séjour en Suisse, se rendre à New-York et y accoucher.
3.1 En l'occurrence, la cour cantonale a considéré que l'intimée n'avait commis aucun abus de droit dès lors que le choix d'un accouchement à New-York avait été pris d'entente entre les parties. Elle s'est référée au fait que le recourant avait transmis à son épouse, le 13 avril 2011, un courriel comportant une liste d'obstétriciens pratiquant dans cette ville et, le 15 mai 2011, un message contenant un lien relatif à un logement à louer à New-York.
3.2 Dans ses écritures, le recourant argue tout d'abord que l'intimée aurait pris unilatéralement la décision d'accoucher à New-York, que son départ, deux mois à peine après le mariage, était planifié avec sa s?ur et un ami et qu'elle le lui a caché jusqu'au dernier moment. Il avance également que l'intimée lui aurait assuré de revenir en Grèce après l'accouchement, raison pour laquelle il s'est acquitté des frais d'accouchement et d'autres factures relatives au séjour à New-York. Il fait ensuite valoir que son accord pour un accouchement dans cette ville fut forcé par les circonstances, précisant que, s'il s'était enquis des prix des soins prénataux aux Etats-Unis, le couple avait finalement écarté l'idée d'un accouchement à l'étranger. Il invoque encore que l'intimée aurait tout planifié et l'aurait épousé dans le seul but de lui réclamer une contribution d'entretien, indiquant qu'elle n'avait aucune raison pour ne pas accoucher en Grèce où tous deux connaissaient de nombreux médecins. Le recourant tente enfin, par de nombreuses allégations relatives au comportement de l'intimée envers les autorités, de démontrer que celle-ci aurait commis un abus de droit en accouchant à New-York et non en Grèce et se plaint de ce que la cour cantonale n'en ait pas tenu compte. Il fait notamment valoir qu'elle ne s'est constituée un nouveau domicile qu'en novembre 2011, que, malgré les prétendues difficultés du couple - qu'il conteste -, elle n'a entrepris des démarches judiciaires qu'à la fin décembre 2011, qu'elle a refusé de l'informer sur les conditions de vie de l'enfant et s'est même opposée à l'exercice de son droit de visite, qu'elle a pris de faux congés-maladie, qu'elle a signé un contrat de troisième année à F._ alors qu'elle ne bénéficie que d'une expérience clinique de six mois, que, bien qu'elle travaillât, elle a perçu des indemnités du fait de son congé-maternité, que, à la naissance de l'enfant, elle n'a pas déclaré le nom du père aux autorités new-yorkaises ni ne lui a donné le nom de celui-ci, qu'elle a également refusé d'indiquer le nom du père de l'enfant dans sa déclaration de résidence, irrégularités qu'elle n'a jamais voulu rectifier.
3.3 Les critiques du recourant, qui se contente de présenter sa propre appréciation des faits en s'appuyant le plus souvent sur des faits et moyens de preuve irrecevables (cf. supra consid. 1.4), en particulier lorsqu'il prétend que les parties auraient finalement décidé que l'accouchement aurait lieu en Grèce, sont essentiellement appellatoires; elles ne permettent en tous les cas pas de qualifier d'insoutenable l'appréciation de la cour cantonale, selon laquelle, au vu des échanges de messages entre les parties, le choix de New-York pour l'accouchement de l'intimée leur était commun. Il en va de même pour l'ensemble des allégations du recourant relatives au prétendu comportement de l'intimée avec les autorités; celles-ci ne sont d'ailleurs pas de nature à démontrer que le choix du lieu de l'accouchement n'avait pas été pris en commun et ne sont donc pas susceptibles d'influer sur l'issue du litige. Le grief du recourant peut ainsi être rejeté, dans la mesure où il est recevable, sans qu'il n'y ait lieu de statuer sur la question de savoir si la mère aurait pu commettre un éventuel abus de droit en décidant d'accoucher à New-York contre la volonté de son époux.
4. Le recourant fait ensuite valoir que la décision entreprise serait arbitraire dans son résultat en tant qu'elle permet à une mère enceinte de quitter son pays pour accoucher à l'étranger, d'éviter la création d'une résidence habituelle de l'enfant dans l'état où vit le père et, ainsi, d'éluder les règles de la CLaH80.
4.1 A teneur de l'art. 4 de la CLaH80, la Convention s'applique à tout enfant qui avait sa résidence habituelle dans un Etat contractant immédiatement avant l'atteinte aux droits de garde ou de visite. L'application de la Convention cesse lorsque l'enfant parvient à l'âge de 16 ans. En outre, le déplacement ou le non-retour d'un enfant est illicite au sens de la Convention, lorsqu'il a lieu en violation d'un droit de garde, attribué à une personne, une institution ou tout autre organisme, seul ou conjointement, par le droit de l'Etat dans lequel l'enfant avait sa résidence habituelle immédiatement avant son déplacement ou son non-retour (art. 3 al. 1 let. a CLaH80).
La notion de résidence habituelle, qui n'est pas définie dans la CLaH80, doit être déterminée de manière autonome (arrêt 5A_257/2011 du 25 mai 2011 consid. 2.2). Selon la définition qu'en donne en règle générale la jurisprudence, la résidence habituelle est basée sur une situation de fait et implique la présence physique dans un lieu donné; la résidence habituelle de l'enfant se détermine ainsi d'après le centre effectif de sa propre vie et de ses attaches (<ref-ruling> consid. 3; 5A_427/2009 du 27 juillet 2009 consid. 3.2 publié in FamPra.ch 2009, p. 1088). En conséquence, outre la présence physique de l'enfant, doivent être retenus d'autres facteurs susceptibles de faire apparaître que cette présence n'a nullement un caractère temporaire ou occasionnel et que la résidence de l'enfant traduit une certaine intégration dans un environnement social et familial; sont notamment déterminants la durée, la régularité, les conditions et les raisons du séjour sur le territoire et du déménagement de la famille, la nationalité de l'enfant, le lieu et les conditions de scolarisation, les connaissances linguistiques ainsi que les rapports familiaux et sociaux de l'enfant (arrêt 5A_889/2011 du 23 avril 2012 consid. 4.1.2; cf. également Arrêt de la CJCE du 2 avril 2009 C-523/07 Korkein hallinto-oikeus contre Finlande, Rec. 2009 I-02805 point 37 ss). La résidence habituelle doit être définie pour chaque personne séparément; cependant, celle d'un enfant coïncide le plus souvent avec le centre de vie d'un des parents, les relations familiales du très jeune enfant avec le parent en ayant la charge étant en règle générale déterminantes (arrêts 5A_650/2009 du 11 novembre 2009 consid. 5.2, publié in SJ 2010 I, p. 193; <ref-ruling> consid. 4.1; cf.également PIRRUNG in: Staudinger, Kommentar zum BGB, 2009, n. D35 Vorbem. zu art. 19 EGBGB; SIEHR in: Münchener Kommentar zum BGB, vol. 10, 2010, n. 30 Anh. I ad art. 21 EGBGB; MAZENAUER, Internationale Kindesentführungen und Rückführungen - Eine Analyse im Lichte des Kindeswohl, 2012, n. 14). Un séjour de six mois crée en principe une résidence habituelle, mais celle-ci peut exister également sitôt après le changement du lieu de séjour, si, en raison d'autres facteurs, elle est destinée à être durable et à remplacer le précédent centre d'intérêts (arrêts 5A_650/2009 du 11 novembre 2009 consid. 5.2, publié in SJ 2010 I, p. 193; 5A_220/2009 du 30 juin 2009 consid. 4.1.2 publié in SJ 2010 I, p. 169; 5A_665/2010 du 2 décembre 2010 consid. 4.1 et les références citées).
4.2 Le recourant invoque que, lors de sa plainte au Ministère grec de la justice, l'intimée et l'enfant n'étaient pas encore domiciliées en Suisse et qu'en conséquence, leur résidence se trouvait en Grèce, où l'intimée était toujours employée de E._. Il ajoute que, même lors du dépôt de sa demande en retour, l'intimée et l'enfant ne résidaient pas encore depuis six mois en Suisse. Il fait par ailleurs valoir que le domicile suisse de l'intimée et de l'enfant est temporaire puisque celle-là prévoit un retour en Grèce après la fin de sa formation et que ce lieu n'a pas été choisi d'un commun accord entre les parties, élément nécessaire, selon le droit américain, pour donner une résidence à l'enfant. Il estime enfin que le choix de la Suisse était planifié car il serait notoire que la loi et les tribunaux de ce pays offrent une large protection aux mères en leur attribuant d'importantes contributions d'entretien.
4.3 La cour cantonale a considéré que C._ n'avait pas pu avoir, en tant que nasciturus, de résidence habituelle en Grèce, quand bien même sa mère y avait le centre de ses intérêts et y était domiciliée durant la grossesse. Elle a ensuite estimé que, n'ayant passé que quelques semaines, à la suite de sa naissance, à New-York, l'enfant n'y avait pas non plus constitué une résidence habituelle. Elle a en revanche constaté que, étant venue en Suisse le 31 août 2011, elle y avait vécu presque l'entier de sa jeune vie avec sa mère, laquelle, à première vue, y séjournera pour plusieurs années en raison de la formation médicale entreprise. La juridiction en a déduit que C._ avait eu sa première résidence habituelle en Suisse, de sorte qu'elle ne saurait y avoir été déplacée illicitement depuis la Grèce, où elle n'avait jamais résidé.
4.4 Ces considérations ne prêtent pas le flanc à la critique. En effet, quand bien même les relations familiales du très jeune enfant avec le parent en ayant la charge sont le plus souvent déterminantes pour établir le centre de sa vie, la résidence habituelle de l'enfant doit être définie séparément de celle de ce parent. Toute résidence implique en outre nécessairement une présence physique à un endroit donné. Il suit de là que le nasciturus ne saurait se constituer une quelconque résidence habituelle. De plus, la CLaH80, comme la Convention de La Haye du 19 octobre 1996 concernant la compétence, la loi applicable, la reconnaissance, l'exécution et la coopération en matière de responsabilité parentale et de mesures de protection des enfants (CLaH 96, RS 0.211.231.011), doit s'appliquer aux enfants dès leur naissance. À cet égard, il y a lieu de noter que la CLaH96 le prévoit expressément (art. 2 CLaH96) et qu'une application de cette Convention aux enfants dès leur conception a été clairement rejetée lors de son élaboration (Rapport explicatif LAGARDE sur la CLaH 96, p. 544; PIRRUNG, in: Staudinger, Kommentar zum BGB, 2009, n. G23 Vorbem. zu art. 19 EGBGB). En conséquence, C._ qui n'a jamais été, en personne, présente physiquement en Grèce, ne saurait y avoir eu une résidence habituelle. Ce motif suffit au rejet de la demande en retour formée par le recourant sans qu'il ne faille examiner si l'enfant s'est valablement constituée une résidence habituelle en Suisse.
5. Le recourant, invoquant la protection de sa sphère privée et familiale, se plaint encore de violation des art. 13 et 36 Cst. et de ses droits découlant de l'art. 8 CEDH. Ces griefs doivent d'emblée être rejetés. La cour cantonale ne s'est nullement prononcée sur l'attribution de l'autorité parentale ou du droit de garde sur l'enfant ou encore sur le droit de visite; elle ne s'est exprimée que sur l'application de la CLaH80 qu'elle a niée. Ces questions sont en revanche l'objet des procédures actuellement pendantes respectivement à Lausanne et en Grèce au cours desquelles l'intérêt du recourant à prendre soin de son enfant ainsi qu'à entretenir des relations avec elle sera pris en compte.
6. Sur le vu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable. Les art. 26 CLaH80 et 14 LF-EEA prévoient la gratuité de la procédure; toutefois, conformément aux dispositions de l'art. 42 CLaH80 et par application de l'art. 26 al. 3 CLaH80, la Grèce a déclaré n'être tenue au paiement des frais visés au deuxième paragraphe de l'article 26 et qui sont liés à la participation d'un avocat ou d'un conseiller juridique ou aux frais de justice, que dans la mesure où ces coûts concernent des cas d'assistance judiciaire ou juridique offerte gratuitement. La Suisse applique dans ce cas le principe de la réciprocité (art. 21 al. 1 let. b de la Convention de Vienne du 23 mai 1969 sur le droit des traités [RS 0.111]), de sorte que la procédure devant le Tribunal fédéral n'est pas gratuite (arrêts 5A_25/2010 du 2 février 2010 consid. 3; 5A_840/2011 du 13 janvier 2012 consid. 6. Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>) arrêtés à 3'000 fr., dont font partie les frais de représentation de l'enfant par 1'000 fr. (5A_840/2011 du 13 janvier 2012 consid. 6). Il versera en outre à l'intimée une indemnité de dépens à hauteur de 2'000 fr. (<ref-law>). Il n'y a enfin pas lieu d'entrer en matière sur la demande d'assistance judiciaire de la curatrice de l'enfant, les frais de représentation de celle-ci étant compris dans les frais judiciaires.

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. (y compris les frais de représentation de l'enfant), sont mis à la charge du recourant.
3. Une indemnité de 2'000 fr., à payer à l'intimée à titre de dépens, est mise à la charge du recourant.
4. Une indemnité de 1'000 fr. est allouée à Me Catherine Jaccottet Tissot, à titre d'honoraires, par la Caisse du Tribunal fédéral.
5. Le présent arrêt est communiqué aux parties, à la Chambre des tutelles du Tribunal cantonal du canton de Vaud, à l'Etat de Vaud, Service de Protection de la Jeunesse, et à l'Office fédéral de la justice, Autorité centrale fédérale.
Lausanne, le 12 juin 2012
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Hohl
Le Greffier: Richard