Faits:
A. A._ est entré en Suisse durant le mois de juillet 2001, où il a déposé une demande d'asile qui a été rejetée. Il a été invité à quitter la Suisse au plus tard le 18 novembre 2003. Un avis de fin de droit relatif aux normes d'assistance lui a été notifié le 12 mars 2008 par le Service des migrations du canton de Neuchâtel.
B. Le 12 juin 2008, A._ et B._ ont déposé une demande en exécution de la procédure préparatoire du mariage auprès de l'Office de l'état civil de Bienne-Nidau (dorénavant: de l'Arrondissement de l'état civil du Seeland; ci-après: l'Office).
B.a Par décision du 4 novembre 2009, l'Office a refusé de célébrer le mariage de A._ et B._, au motif que l'identité du fiancé n'était pas prouvée.
Par arrêt du 30 juillet 2010, la Direction de la police et des affaires militaires du canton de Berne (ci-après: POM) a admis le recours des fiancés, annulé la décision du 4 novembre 2009 et invité l'Office à vérifier l'authenticité des documents d'identité du fiancé.
Par lettre recommandée du 21 février 2011, l'Office a imparti un délai de 60 jours au fiancé pour attester la légalité de son séjour en Suisse. Le fiancé n'a pas établi la légalité de son séjour à l'échéance de ce délai.
B.b Par décision du 16 mai 2011, l'Office a confirmé son refus de poursuivre la procédure de préparation en vue du mariage de A._ et B._, le fiancé n'ayant pas établi la légalité de son séjour dans le délai imparti.
La POM a, par arrêt du 18 janvier 2012, rejeté le recours des fiancés contre la décision précitée.
Le 17 février 2012, les fiancés ont déposé un recours à la 2ème Chambre civile de la Section civile de la Cour suprême du canton de Berne (ci-après: la Cour suprême).
Par ordonnance du 23 avril 2012, un délai de vingt jours a été imparti aux fiancés pour se prononcer sur la prise de position de la POM et pour déposer une éventuelle autorisation de séjour délivrée au fiancé.
Par courrier du 11 mai 2012, les fiancés ont requis la suspension de la procédure, subsidiairement, un délai pour produire le titre de séjour du fiancé, une demande d'autorisation de séjour étant pendante devant l'Office de la Sécurité publique et de la population de la Ville de Bienne. Par ordonnance du 21 mai 2012, le Juge instructeur de la Cour suprême a rejeté la demande de suspension et de prolongation.
Statuant par arrêt du 21 juin 2012, la Cour suprême a rejeté le recours des fiancés contre la décision de la POM du 18 janvier 2012.
C. Par acte du 24 août 2012, les fiancés interjettent un recours en matière civile au Tribunal fédéral, concluant à ce que l'arrêt entrepris soit annulé et principalement à sa réforme en ce que la continuation de la procédure préparatoire du mariage entre les recourants est autorisée, subsidiairement, au renvoi de la cause à l'Office d'état civil pour nouvelle décision. Les recourants se plaignent de la violation du droit international, du principe de la sécurité du droit et du droit fédéral, en particulier de l'art. 98 al. 4 CC, ainsi que d'arbitraire dans l'établissement des faits et l'appréciation des preuves (art. 9 Cst.).
Des réponses n'ont pas été requises.
Considérant en droit:
1. L'arrêt attaqué portant sur le refus de poursuivre la procédure préparatoire du mariage, en application de l'art. 98 al. 4 CC, est une décision finale selon l'art. 90 LTF (arrêt 5A_814/2011 du 17 janvier 2012 consid. 1), prise en application de normes de droit public, notamment de droit des étrangers, dans une matière connexe au droit civil (art. 72 al. 2 let. b ch. 2 LTF; arrêts 5A_814/2011 du 17 janvier 2012 consid. 1, 5A_225/2011 du 9 août 2011 consid. 1.1). Interjeté dans le délai (art. 46 al. 1 let. b et 100 al. 1 LTF) et dans la forme (art. 42 LTF) prévus par la loi, par des parties qui ont succombé dans leurs conclusions prises devant l'autorité précédente et ont un intérêt digne de protection à l'annulation ou à la modification de l'arrêt entrepris (art. 76 al. 1 LTF), contre une décision prise sur recours par un tribunal supérieur statuant en dernière instance cantonale (art. 75 al. 1 et 2 LTF), le présent recours en matière civile est en principe recevable.
2. 2.1 Le recours en matière civile peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF). Cela étant, eu égard à l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (art. 108 al. 1 let. b LTF), il n'examine en principe que les griefs soulevés; il n'est pas tenu de traiter, à l'instar d'une autorité de première instance, toutes les questions juridiques pouvant se poser, lorsque celles-ci ne sont plus discutées devant lui (ATF 135 III 397 consid. 1.4 p. 400; 134 III 102 consid. 1.1 p. 104). Par exception à la règle selon laquelle il applique le droit d'office, il ne peut entrer en matière sur la violation d'un droit fondamental que si le grief a été invoqué et motivé de manière précise par la partie recourante (art. 106 al. 2 LTF; ATF 137 II 305 consid. 3.3 p. 310 s.; 134 I 83 consid. 3.2 p. 88). Si le recourant se plaint de la violation de droits constitutionnels, il doit ainsi satisfaire au principe d'allégation (Rügeprinzip); le Tribunal fédéral n'examine la violation de ces droits que s'ils ont été expressément soulevés et exposés de façon claire et détaillée (ATF 135 III 232 consid. 1.2 p. 234; 133 II 249 consid. 1.4.2 p. 254).
2.2 Le Tribunal fédéral conduit son raisonnement sur la base des faits établis par la juridiction précédente (art. 105 al. 1 LTF); 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'art. 95 LTF (art. 105 al. 2 LTF), et si la correction du vice est susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF). Le recourant qui soutient que les faits ont été constatés d'une manière manifestement inexacte (art. 97 al. 1 LTF), c'est-à-dire arbitraire au sens de l'art. 9 Cst. (ATF 133 II 249 consid. 1.2.2 p. 252), doit satisfaire au principe d'allégation susmentionné (cf. supra consid. 2.1).
2.3 Les recourants produisent un lot de cinq pièces à l'appui de leur recours.
2.3.1 Les faits et moyens de preuve nouveaux sont prohibés, à moins de résulter de la décision de l'autorité précédente (art. 99 al. 1 LTF; ATF 135 I 221 consid. 5.2.4 p. 229; 133 IV 342 consid. 2.1 p. 344). Ainsi, il n'est pas possible de se prévaloir devant le Tribunal fédéral de pièces qui n'ont pas été produites en procédure cantonale, alors qu'elles auraient pu l'être en temps utile. Les pièces postérieures à l'arrêt entrepris sont en outre d'emblée irrecevables (ATF 133 IV 342 consid. 2.1 p. 343 s.; arrêt 5A_640/2011 du 4 janvier 2012 consid. 1.4).
2.3.2 Sont dès lors d'emblée irrecevables, les lettres de la ville de Bienne des 10 juillet et 20 août 2012, ces pièces étant postérieures à l'arrêt querellé. Par ailleurs, les recourants n'alléguant pas, ni a fortiori ne démontrant, que la production de pièces en instance fédérale serait devenue nécessaire à la suite de l'arrêt entrepris, la lettre que le conseil des recourants a adressée à la ville de Bienne le 7 juin 2012 est également irrecevable, indépendamment de sa pertinence. Quant au courrier que le conseil des fiancés a adressé à la mairie de Bienne le 22 mars 2012 et à la lettre de la ville de Bienne du 25 avril 2012, ces pièces ont été produites par les recourants devant l'autorité précédente à l'appui de la requête de suspension du 11 mai 2012, en sorte qu'elles ont déjà été versées au dossier de la cause.
3. Le litige a pour objet le refus de la continuation d'une procédure préparatoire de mariage entre une suissesse et un étranger séjournant illégalement en Suisse, fondé sur l'art. 98 al. 4 CC, à teneur duquel, "[l]es fiancés qui ne sont pas citoyens suisses doivent établir la légalité de leur séjour en Suisse au cours de la procédure préparatoire".
La Cour suprême a rejeté le grief de la constatation arbitraire des faits, estimant qu'il ne ressortait pas de la décision de la POM que celle-ci aurait refusé la préparation du mariage sous prétexte que cette union serait fictive. Se référant à la jurisprudence en la matière (arrêt 5A_814/2011 du 17 janvier 2012), elle a relevé que l'autorité inférieure n'avait aucune marge de man?uvre pour évaluer la sincérité des sentiments des fiancés, dans le cadre de l'art. 98 al. 4 CC. Les juges cantonaux ont admis que l'autorité de l'état civil avait, sans arbitraire, uniquement contrôlé si les conditions légales à la poursuite d'une procédure préparatoire en vue du mariage étaient remplies. Quant à la prise en considération de la situation dans le pays d'origine du fiancé et la demande de production d'un duplicata du passeport de celui-ci muni d'un timbre officiel, l'autorité précédente a relevé que cette constatation n'était pas pertinente parce qu'il n'avait pas été tenu compte du problème d'établissement de l'identité du fiancé dans la décision de l'Office, le refus de continuer la procédure préparatoire étant fondé sur le défaut d'autorisation de séjour en Suisse.
S'agissant de la violation du droit international et du principe de proportionnalité, la cour cantonale a retenu que l'autorité compétente en matière de droit des étrangers avait été saisie le 25 avril 2012 seulement, alors que les fiancés avaient été invités à requérir une autorisation de séjour plus d'un an auparavant, par lettre recommandée de l'Office du 21 février 2011, leur impartissant un délai de soixante jours à cet effet, et qu'un délai supplémentaire de vingt jours leur avait encore été imparti par ordonnance du 23 avril 2012 du Juge instructeur.
La Cour suprême a enfin considéré dénuée de fondement la critique portant sur la prétendue insuffisance du délai de deux mois imparti au fiancé pour attester de la légalité de son séjour, considérant que ce délai était conforme à la Directive n° 10.11.01.02 faisant suite à l'entrée en vigueur de l'art. 98 al. 4 CC. Elle a constaté qu'au terme de ce délai, les recourants n'avaient pas établi la légalité du séjour du fiancé devant la POM et que le second délai de vingt jours que le Juge instructeur a imparti aux recourants n'avait pas non plus été respecté, les fiancés ayant toutefois déposé une demande de permis de séjour le 22 mars 2012.
4. Les recourants font grief à l'autorité précédente d'avoir fondé son raisonnement sur un arrêt du Tribunal fédéral (arrêt 5A_814/2011 du 17 janvier 2012) rendu la veille de la décision de la POM, autrement dit sur une jurisprudence dont ils n'avaient pas connaissance lors du dépôt de leur recours, violant ainsi le "principe de sécurité du droit".
En l'occurrence, l'arrêt cité par les recourants (5A_814/2011, ATF 138 I 41 consid. 4 et 5) ne s'écarte pas de l'ATF 137 I 351 (arrêt 2C_349/2011 du 23 novembre 2011), dont les recourants ont eux-mêmes fait état dans leur recours à la Cour suprême. Quoi qu'il en soit, l'on ne voit pas - et les fiancés n'explicitent pas leur critique - en quoi la cour cantonale aurait fait preuve d'arbitraire en justifiant son raisonnement par une jurisprudence constante antérieure à la décision qu'elle examine et pertinente dans le cas d'espèce. Le grief est ainsi mal fondé, autant qu'il est recevable (art. 42 al. 2 LTF, cf. supra consid. 2.1).
5. Les recourants se plaignent ensuite de la constatation inexacte des faits par l'autorité précédente (art. 9 Cst.).
5.1 Les fiancés critiquent le refus des juges cantonaux de reconnaître la sincérité des sentiments des fiancés, partant la prémisse erronée qu'il s'agirait d'un mariage de complaisance. Ils reprochent aussi à l'autorité précédente d'avoir méconnu l'existence de deux procédures parallèles civile et administrative, parce que le fiancé devait obtenir la légalisation de son séjour en même temps que se déroule la phase préparatoire du mariage. Ils ajoutent à ce sujet que la cour suprême a méconnu le fait que le dossier de demande de préparation au mariage a été déposé en 2008. Les fiancés se plaignent encore du fait que les juges cantonaux ont ignoré la situation du pays d'origine du fiancé, qui ne lui permettait pas d'obtenir rapidement les documents requis, et les échanges de courriers produits relatifs à la procédure d'obtention d'une autorisation de séjour, ce qui a eu pour incidence la fixation au fiancé d'un délai trop bref pour produire une autorisation de séjour.
5.2 Pour autant que l'on admette que la critique respecte les exigences de motivation posées par l'art. 106 al. 2 LTF (cf. supra, consid. 2.1 et 2.2), les recourants se limitant de manière générale à présenter leur version de la cause sans se référer à des passages précis de l'arrêt entrepris et sans expliquer l'incidence de chacune des constatations sur l'issue du litige, force est de constater qu'elle est mal fondée.
Il apparaît dans la décision attaquée que la procédure préparatoire du mariage a été introduite le 12 juin 2008 auprès de l'Office de l'état civil, en sorte que ce constat est conforme à ce que les recourants entendent faire reconnaître.
S'agissant de la sincérité des sentiments des époux, cette constatation de fait n'est pas pertinente pour l'issue du litige, cet élément ne figurant pas au titre de condition à l'art. 98 al. 4 CC. A défaut de disposition transitoire, cette dernière disposition est applicable dès le 1er janvier 2011 à toute procédure préparatoire de mariage pendante (art. 1er Tit. fin CC; FF 2008 2247, p. 2254; ch. 5 p. 8 de la Directive 10.11.01.02 de l'OFEC du 1er janvier 2011), sans égard à la date d'introduction de la demande d'ouverture de la procédure. En l'espèce, la procédure de préparation du mariage des recourants n'était pas formellement close au sens de l'art. 99 al. 2 CC le 1er janvier 2011. La loi exigeant depuis cette date que le fiancé étranger prouve la légalité de son séjour en requérant une autorisation à l'autorité compétente en matière de police des étrangers, la sincérité des sentiments ne dispensait donc pas les recourants d'apporter à l'Office la preuve de la légalité du séjour prévue à l'art. 98 al. 4 CC.
Pour le surplus, il ressort de l'arrêt attaqué que l'autorité précédente a tenu compte de la situation du pays d'origine du fiancé, des échanges de courriers produits (cf. supra consid. 2.3.2 in fine) et de la procédure administrative parallèle, la Cour suprême ayant relevé que le problème de la légalité du séjour en Suisse du fiancé et de son identité étaient cependant connus des recourants dès le 4 novembre 2009 lorsque l'Office a refusé de continuer la procédure préparatoire du mariage, partant, que les fiancés avaient tardé à s'adresser à l'autorité compétente en matière de droit des étrangers. Il s'ensuit que les recourants se méprennent lorsqu'ils estiment que l'autorité cantonale a omis de tenir compte des éléments susdésignés.
Le grief d'arbitraire dans l'établissement des faits et l'appréciation des preuves (art. 9 Cst.) doit donc être rejeté, dans la mesure de sa recevabilité (art. 106 al. 2 LTF, cf. supra consid. 2.1 et 2.2).
6. Les recourants font enfin grief à la cour cantonale d'avoir violé le droit international (art. 8 et 12 de la Convention des droits de l'Homme, CEDH) et fédéral (art. 13 et 14 Cst., art. 98 al. 4 CC) par une interprétation trop restrictive de l'exigence de la légalisation du séjour en Suisse du fiancé, ne respectant pas l'application préconisée par le Tribunal fédéral dans sa jurisprudence, partant conduisant à mettre un obstacle prohibitif au mariage et à fixer un délai trop bref au fiancé pour prouver la légalité de son séjour. Ils reprochent en outre aux juges précédents d'être partis de la prémisse erronée qu'il s'agissait d'un mariage de complaisance.
6.1 Dans son arrêt du 23 novembre 2011 (ATF 137 I 351), la IIe Cour de droit public du Tribunal fédéral, saisie d'un recours contre une décision de refus d'entrée en matière sur une demande d'autorisation de séjour en vue de mariage, a examiné la conformité de la législation suisse avec le droit au mariage garanti par l'art. 12 CEDH et avec la jurisprudence de la CourEDH. Ainsi qu'elle l'a précisé dans son arrêt du 17 janvier 2012 (5A_814/2011), la IIe Cour de droit civil fait siens les motifs exposés par la IIe Cour de droit public quant à la conformité de la législation suisse avec l'art. 12 CEDH et à la répartition des compétences respectives des autorités de police des étrangers et de l'officier de l'état civil.
Selon la jurisprudence, le système mis en place par le législateur à l'art. 98 al. 4 CC serait contraire à l'art. 12 CEDH si l'autorité de police des étrangers venait à présumer de manière irréfragable qu'un étranger démuni d'un titre de séjour en Suisse ne peut avoir qu'une volonté viciée de se marier, sans égard à la durée et à la stabilité de sa relation et aux éventuels enfants nés de celle-ci et si elle était ainsi amenée à interdire, de manière générale, automatique et indifférenciée, l'exercice du droit au mariage pour toute une catégorie de personnes (ATF 137 I 351 consid. 3.5 p. 356 ss, arrêt 5A_814/2011 du 17 janvier 2012 consid. 4). Il appartient ainsi à l'autorité cantonale compétente en matière de police des étrangers de prendre en compte, lorsqu'elle statue sur une demande d'autorisation de séjour en vue du mariage, les exigences liées au respect du droit au mariage et au principe de la proportionnalité. L'officier de l'état civil, saisi d'une demande d'ouverture de la procédure préparatoire en vue du mariage, ne dispose d'aucune marge de manoeuvre lorsque le fiancé étranger n'a pas établi la légalité de son séjour en Suisse, conformément à l'art. 98 al. 4 CC: il doit refuser d'entrer en matière sur la demande de mariage (ATF 137 I 351 consid. 3.7 p. 359 s.; arrêt 5A_814/2011 du 17 janvier 2012 consid. 4). Même si l'autorité de police des étrangers n'a pas été préalablement saisie d'une demande d'autorisation de séjour, l'art. 98 al. 4 CC ne permet pas à l'officier de l'état civil de statuer préjudiciellement sur la légalité du séjour. Néanmoins, afin de respecter le principe de la proportionnalité et d'éviter tout formalisme excessif, celui-ci devra fixer au fiancé étranger un délai suffisant pour saisir l'autorité compétente et produire l'attestation de la légalité de son séjour en Suisse (arrêt 5A_814/2011 du 17 janvier 2012 consid. 5).
6.2 En l'occurrence, dès l'entrée en vigueur de l'art. 98 al. 4 CC, l'Office a imparti aux recourants, par lettre recommandée du 21 février 2011, un délai de soixante jours pour établir la légalité du séjour du fiancé en Suisse. Plus d'un an après l'échéance de ce premier délai non-utilisé, l'autorité précédente a fixé aux recourants, par ordonnance du 23 avril 2012, un nouveau délai de vingt jours pour produire l'autorisation de séjour en Suisse du fiancé (cf. supra consid. 3). Ce délai n'a pas non plus été mis à profit. Les recourants ont par ailleurs disposé de plus d'un an depuis l'introduction de l'art. 98 al. 4 CC pour obtenir les documents nécessaires, partant, pour prouver la légalité du séjour du fiancé. Le délai laissé aux recourants pour amener la preuve de la légalité du séjour du fiancé n'était ainsi pas contraire au droit fédéral, ni a fortiori arbitraire (arrêt 5A_814/2011 du 17 janvier 2012 consid. 5), d'autant que la Cour suprême a encore attendu un mois après son refus de suspendre la procédure ou prolonger le délai de production d'une autorisation de séjour, pour statuer. Contrairement à ce que soutiennent les recourants, la production de l'échange de courriers avec les autorités administratives en matière de droit des étrangers n'est au demeurant pas de nature à prouver le séjour légal en Suisse du fiancé (art. 84 al. 2 OEC; ch. 2.2 p. 4 s. de la Directive 10.11.01.02 de l'OFEC du 1er janvier 2011). L'exigence de l'établissement de la légalité du séjour, tel qu'appliqué en l'espèce par la production d'une autorisation de séjour dans un premier délai de soixante jours, puis - plus d'un an plus tard - dans un second délai de vingt jours, ne représentait pas en définitive une exigence excessive et résulte d'une interprétation de l'art. 98 al. 4 CC conforme à la jurisprudence. Ainsi qu'il a déjà été exposé, l'éventuelle prémisse d'un mariage de complaisance n'a eu aucune incidence sur l'application de la norme par les autorités de l'état civil qui ne statuent pas sur l'octroi d'un titre de séjour, mais se limitent à constater son existence (cf. supra consid. 5.2 et 6.1). Dans ces conditions, la continuation de la préparation du mariage ne pouvait qu'être refusée, dès lors que la preuve de la légalité du séjour n'avait pas été rapportée à l'échéance du délai supplémentaire, ni même lorsque les juges précédents ont statué. L'autorité cantonale a en définitive interprété la norme conformément à la jurisprudence de la CourEDH et fédérale. Les griefs de violation des art. 8 et 12 CEDH, 13 et 14 Cst., et de l'art. 98 al. 4 CC sont en définitive mal fondés.
7. Vu ce qui précède, le recours doit être rejeté, dans la mesure de sa recevabilité. Les frais judiciaires sont mis solidairement à la charge des recourants qui succombent (art. 66 al. 1 et 5 LTF). L'autorité intimée, qui n'a d'ailleurs pas été invitée à déposer des observations, n'a pas droit à l'allocation de dépens (art. 68 al. 3 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 à 2'000 fr., sont mis solidairement à la charge des recourants.
3. Le présent arrêt est communiqué aux recourants, à l'Arrondissement de l'état civil du Seeland et à la 2e Chambre civile de la Section civile de la Cour suprême du canton de Berne.
Lausanne, le 19 novembre 2012
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Hohl
La Greffière: Carlin