Faits:
A. A.a Y._, ressortissant brésilien né en 1976, est entré en Suisse en novembre 2007 au bénéfice d'un visa touristique. Il a été interpellé par la police le 20 novembre 2007 alors qu'il s'adonnait à la prostitution. Il lui a été donné l'ordre de quitter la Suisse d'ici au 10 décembre 2007. Interpellé une nouvelle fois au mois d'avril 2008, l'intéressé a reconnu être resté en Suisse et avoir poursuivi ses activités de prostitution. L'Office fédéral des migrations a prononcé une interdiction d'entrée à son encontre le 28 avril 2008.
A.b Le 10 juin 2008, Y._ a sollicité une autorisation de séjour en vue de conclure un partenariat enregistré avec X._, ressortissant suisse né en 1936. Le Service de la population du canton de Vaud a refusé celle-ci par décision du 4 novembre 2008, laquelle fait l'objet d'un recours pendant devant la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud.
A.c En parallèle, le 18 juin 2008, Y._ et X._ ont présenté une demande d'ouverture d'un dossier d'enregistrement d'un partenariat à l'Office de l'état civil du Nord vaudois.
Les candidats au partenariat ont été entendus séparément le 28 octobre 2008 par l'Officier d'état civil. Celui-ci a transmis le dossier des intéressés à la Direction de l'état civil du canton de Vaud, laquelle les a convoqués pour une seconde audition. Le 16 mars 2009, la Direction de l'état civil a retourné le dossier à l'Office de l'état civil, en l'informant qu'elle était d'avis que l'ensemble des éléments pris en considération permettait de conclure que l'on se trouvait en présence d'un partenariat enregistré de complaisance.
B. B.a Par décision du 27 mars 2009, l'Officier de l'état civil du Nord vaudois a refusé son concours à l'enregistrement du partenariat de Y._ et X._.
B.b Par arrêt du 27 juillet 2009, la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud a rejeté le recours déposé par les intéressés et confirmé la décision attaquée.
C. Y._ et X._ interjettent le 20 août 2009 un recours en matière de droit public et un recours constitutionnel subsidiaire au Tribunal fédéral contre cet arrêt, concluant à ce qu'il soit annulé, de même que la décision du 27 mars 2009 de l'Office d'état civil du canton de Vaud [recte: de l'Office de l'état civil du Nord vaudois], et à ce qu'ils puissent conclure un partenariat enregistré. Les recourants se plaignent d'une violation de l'art. 2 de Loi fédérale du 18 juin 2004 sur le partenariat enregistré entre personnes du même sexe (RS 211.231; LPart), 75f de l'Ordonnance du 28 avril 2004 sur l'état civil (RS 211.112.2; OEC), du droit au respect de la vie privée et familiale (art. 13 Cst. et 8 CEDH), du droit à l'égalité de traitement et à l'interdiction de discrimination (art. 8 Cst.), des principe de proportionnalité et de la légalité (art. 5 Cst.), de l'interdiction de l'arbitraire (art. 9 Cst.) et du droit d'être entendu (art. 29 Cst.).
La cour cantonale a renoncé à déposer une réponse. La Direction de l'état civil du canton de Vaud se réfère aux considérants de la décision du 27 mars 2009 de l'Office de l'état civil du Nord vaudois et de l'arrêt attaqué. L'Office fédéral des migrations conclut au rejet du recours. L'Office fédéral de la justice a renoncé à se déterminer.
Par ordonnance du 20 octobre 2009, la requête d'effet suspensif présentée par les recourants a été rejetée.
Considérant en droit:
1. 1.1 Le recours est dirigé contre une décision de l'Officier de l'état civil de refuser son concours à l'enregistrement du partenariat, en application de l'art. 6 al. 2 LPart. Il s'agit d'une décision 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; cf. GEISER/BUSSLINGER, in Ausländerrecht: eine umfassende Darstellung der Rechtsstellung von Ausländerinnen und Ausländern in der Schweiz, 2e éd. 2009, n° 14.10 p. 663). Partant, la voie du recours en matière civile est en principe ouverte.
L'intitulé erroné d'un recours ne nuit pas à son auteur, pour autant que les conditions de recevabilité du recours qui aurait dû être interjeté soient réunies (ATF 134 III 379 consid. 1.2 p. 382 et les arrêts cités).
Interjeté dans le délai légal (art. 100 al. 1 LTF) par des parties qui ont succombé dans leurs conclusions prises devant l'autorité précédente (art. 76 al. 1 LTF) et dirigé contre une décision finale (art. 90 LTF) rendue par la dernière juridiction cantonale (art. 75 al. 1 LTF), le présent recours est recevable en tant que recours en matière civile.
Il s'ensuit que la voie du recours constitutionnel n'est pas ouverte, celui-ci étant ainsi irrecevable (art. 113 LTF).
1.2 Le recours en matière civile peut être formé notamment pour violation du droit fédéral (art. 95 let. a LTF), qui comprend les droits constitutionnels (ATF 133 III 446 consid. 3.1 p. 447, 462 consid. 2.3 p. 466), et du droit international (art. 95 let. b LTF). Le Tribunal fédéral applique en principe le droit d'office (art. 106 al. 1 LTF), 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 (ATF 133 III 545 consid. 2.2 p. 550). Compte tenu des exigences de motivation posées, sous peine d'irrecevabilité (art. 108 al. 1 let. b LTF), à l'art. 42 al. 2 LTF, le Tribunal fédéral n'examine en principe que les griefs soulevés; il n'est pas tenu de traiter, à l'instar d'une juridiction de première instance, toutes les questions juridiques pouvant se poser lorsqu'elles ne sont plus discutées devant lui (ATF 133 IV 150 consid. 1.2 p. 152). Il ne connaît de la violation de droits fondamentaux que si ce grief a été soulevé et motivé par le recourant (art. 106 al. 2 LTF; ATF 134 II 349 consid. 3 p. 351/352 et les arrêts cités).
1.3 Le Tribunal fédéral statue sur la base des faits établis par l'autorité 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'influencer le sort de la cause (art. 97 al. 1 LTF). Le recourant qui soutient que les faits ont été établis de manière manifestement inexacte (art. 97 al. 1 LTF), à savoir que les constatations de fait sont arbitraires au sens de l'art. 9 Cst. (ATF 133 II 249 consid. 1.2.2 p. 252), doit démontrer, par une argumentation précise, en quoi consiste la violation.
2. Les recourants reprochent à la cour cantonale d'avoir violé leur droit d'être entendu en n'ordonnant ni débats, ni audience, alors qu'ils l'avaient requis. Ils sollicitent du Tribunal fédéral la tenue d'une audience ou, subsubsidiairement, de débats, ainsi que le droit de déposer un mémoire complémentaire.
2.1 En vertu de l'art. 6 § 1 CEDH, toute personne a droit à ce que sa cause soit entendue publiquement (ATF 130 II 425 consid. 2.2 p. 429; 121 I 30 consid. 5d p. 35), ce qui signifie qu'à un stade du procès au moins le tribunal doit tenir des débats publics (ATF 121 I 30 consid. 5e p. 35).
En l'espèce, la cour cantonale a compris la requête d'audience et de débats des recourants comme une offre de preuve, qu'elle a rejetée par appréciation anticipée. Les juges précédents ont rappelé à cet égard que, selon la jurisprudence, le droit d'être entendu découlant de l'art. 29 al. 2 Cst. ne comprend pas le droit d'être entendu oralement, ni celui d'obtenir l'audition de témoins; l'autorité peut donc mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves proposées, elle a la certitude qu'elles ne pourraient l'amener à modifier son opinion (ATF 130 II 425 consid. 2.1 p. 428). En l'espèce, la cour cantonale a estimé qu'il n'était pas nécessaire de procéder à d'autres mesures d'instruction, le dossier étant complet et lui permettant de statuer; de plus, les parties avaient eu l'occasion de faire valoir leur point de vue à l'occasion d'un second échange d'écritures.
Par leur critique, les recourants ne s'en prennent pas à l'appréciation de leur requête par les juges cantonaux et ne démontrent pas en quoi il était arbitraire de l'interpréter comme une requête d'administration de preuve. Partant, leur grief est irrecevable.
2.2 Les recourants sollicitent du Tribunal fédéral "la tenue d'une audience ou subsidiairement de débats", sans plus ample précision. Ils requièrent ensuite de pouvoir déposer un mémoire complémentaire (droit de réplique) et demandent que la cour de céans puisse revoir leur situation en fait et en droit, avec une pleine cognition. De cette manière, ils n'indiquent pas clairement s'ils font valoir par là un droit à des débats publics ou un droit à l'administration de preuves devant le Tribunal fédéral.
L'obligation d'organiser des débats publics devant la cour de céans ne s'impose pas lorsque le recours ne soulève aucune question de fait ou de droit qui ne puisse être jugée de manière appropriée sur la base des pièces du dossier (art. 57 LTF; Jean-Maurice Frésard, in Commentaire de la LTF, Berne 2009, n° 9 et 10 ad art. 57 LTF). Comme le Tribunal fédéral est lié par les faits constatés dans l'arrêt cantonal (art. 105 al. 1 LTF), il ne procède pas à l'administration de preuves; si des faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF (cf. art. 105 al. 2 LTF) et qu'il y a lieu de procéder à une administration de preuves, il renvoie la cause à l'autorité cantonale (cf. art. 107 al. 2 LTF).
En l'espèce, les recourants ne prétendent pas que les faits retenus dans la décision attaquée soient manifestement inexacts. Il n'y a donc pas lieu de renvoyer la cause pour procéder à des débats. La requête est rejetée.
2.3 Conformément à l'art. 58 LTF, le Tribunal fédéral délibère en audience si le président l'ordonne, si un juge le demande ou s'il n'y a pas unanimité. Dans les autres cas, le Tribunal fédéral statue par voie de circulation. En l'espèce, aucune des conditions prévues par l'art. 58 LTF n'étant réalisée, la requête tendant à la tenue d'une audience est rejetée et le Tribunal fédéral statue par voie de circulation.
2.4 Quant au droit de réplique, l'art. 102 al. 3 LTF prévoit qu'en règle générale, il n'y a pas d'échange ultérieur d'écritures. Un droit de réplique, découlant du droit d'être entendu, doit être admis lorsque la réponse de l'autorité précédente contient des éléments nouveaux décisifs (ATF 132 I 42 consid. 3.3.4 p. 47; 133 I 98 consid. 2.1 p. 99).
En l'espèce, ni l'intimée, qui s'est référée à l'arrêt attaqué, ni l'Office fédéral des migrations, qui a conclu au rejet du recours, n'ont ajouté d'éléments dans leurs déterminations, alors que la cour cantonale et l'Office fédéral de la justice ont renoncé à déposer une réponse. Dans ces circonstances, il n'y a pas lieu d'ordonner une réplique.
3. Les recourants se plaignent d'une violation du principe de double instance cantonale instauré par la Loi sur le Tribunal fédéral, ainsi que de leur droit d'être entendus, dans la mesure où la voie de recours auprès de l'autorité de surveillance des offices de l'état civil, à savoir le Département de l'intérieur vaudois (cf. art. 1 al. 2, 7 al. 1 et 31 al. 1 de la Loi vaudoise du 25 novembre 1987 sur l'état civil [LEC; RSV 211.11],) représenté par la Direction de l'état civil, ne leur était pas ouverte du fait que celle-ci avait été consultée dans le cadre de la procédure devant l'Officier de l'état civil du Nord vaudois.
Conformément à l'art. 75 al. 2 LTF, les cantons doivent instituer des tribunaux supérieurs comme autorités cantonales de dernière instance, qui statuent sur recours. En l'espèce, cette exigence - qui au demeurant n'est pas encore en vigueur et ne devrait le devenir qu'avec l'introduction du code de procédure civile suisse (art. 130 al. 2 LTF) - a été respectée, puisque la cour cantonale qui a statué sur recours est une autorité de dernière instance. En réalité, les recourants se plaignent de n'avoir pas bénéficié d'une triple instance cantonale. Ils n'invoquent cependant aucune disposition légale cantonale qui leur y aurait donné droit et aurait été violée. Partant, leur grief est infondé.
4. 4.1 Les recourants se plaignent ensuite d'une violation du principe de la légalité. Ils soutiennent que les Directives de l'Office fédéral de l'état civil du 5 décembre 2007 sur l'abus lié à la législation sur les étrangers (refus de célébrer de l'officier de l'état civil, inscription des jugements d'annulation, reconnaissance et transcription d'unions étrangères; directive n° 10.07.12.01), auxquelles se réfèrent les autorités précédentes, et les critères retenus par l'Officier de l'état civil pour décider d'ouvrir une enquête ou de ne pas enregistrer un partenariat devraient faire l'objet d'une ordonnance ou d'une loi, "vu leur importance sur des droits fondamentaux de l'homme (droit de conclure un partenariat, droit de se marier) et leur application à un nombre indéterminé de personnes", et ne pas être seulement des documents internes et inaccessibles.
4.2 Le principe de la légalité est consacré à l'art. 5 al. 1 Cst., selon lequel le droit est la base et la limite de l'activité de l'État. Il en résulte en particulier que toute restriction à un droit fondamental doit - sous réserve des cas de danger sérieux, direct et imminent - être fondée sur une base légale; s'il s'agit d'une restriction grave, elle doit être prévue par une loi (art. 36 al. 1 Cst.; ATF 132 I 229 consid. 10.1 p. 242). Afin d'assurer l'application uniforme de certaines dispositions légales, l'administration peut expliciter l'interprétation qu'elle leur donne dans des directives. Celles-ci n'ont pas force de loi et ne lient ni les administrés, ni les tribunaux, ni même l'administration. Elles ne dispensent pas cette dernière de se prononcer à la lumière des circonstances du cas d'espèce. Par ailleurs, elles ne peuvent sortir du cadre fixé par la norme supérieure qu'elles sont censé concrétiser. En d'autres termes, à défaut de lacune, elles ne peuvent prévoir autre chose que ce qui découle de la législation ou de la jurisprudence (ATF 133 II 305 consid. 8.1 p. 315; 121 II 473 consid. 2b p. 478 et les références).
4.3 En l'espèce, les recourants ne soutiennent pas que les directives en question, qui sont fondées sur l'art. 84 al. 1 let. a OEC et sont accessibles au public sur le site internet de l'Office fédéral de l'état civil (www.ofec.admin.ch), seraient contraires à l'art. 6 al. 2 LPart. Partant, leur critique est infondée.
5. 5.1 Selon l'art. 5 al. 1 LPart, l'officier de l'état civil du domicile de l'un des partenaires est compétent pour enregistrer le partenariat. Il peut refuser son concours à l'enregistrement lorsque l'un des partenaires ne veut manifestement pas mener une vie commune, mais éluder les dispositions sur l'admission et le séjour des étrangers (art. 6 al. 2 LPart).
La célébration du mariage connaît une réglementation identique à l'art. 97a CC, introduit par la Loi fédérale du 16 décembre 2005 sur les étrangers (RS 142.20; LEtr). Il s'agit d'une concrétisation du principe de l'interdiction de l'abus de droit prévue à l'art. 2 al. 2 CC. Pour que l'officier de l'état civil puisse refuser son concours, deux conditions cumulatives doivent être remplies (cf. GEISER/BUSSLINGER, op. cit., n° 14.12, p. 664; GEISER, in Zürcher Kommentar zum Partnerschaftsgesetz, 2007, n° 24 ad art. 5-8 LPart, p. 59). D'une part, les intéressés ne doivent avoir aucune volonté de mener une vie commune. Cette notion renvoie à l'art. 2 al. 2 LPart: les deux personnes s'engagent à mener une vie de couple (Lebensgemeinschaft dans le texte allemand) et à assumer l'une envers l'autre les droits et les devoirs découlant du partenariat (art. 12 ss LPart); il faut entendre par là que les deux partenaires doivent avoir la volonté de fonder une communauté de vie d'une certaine durée, à caractère en principe exclusif, qui présente une composante tant spirituelle que corporelle et économique (GEISER, op. cit., nos 9 ss ad art. 1-2 LPart). D'autre part, les intéressés doivent avoir l'intention d'éluder les dispositions sur l'admission et le séjour des étrangers. La réalisation de ces deux conditions doit être manifeste. Si l'officier de l'état civil a de bonnes raisons de penser qu'il se trouve face à un cas d'abus, il est tenu de poursuivre ses investigations (Message du Conseil fédéral relatif à la loi fédérale sur le partenariat enregistré entre personnes du même sexe du 29 novembre 2002, in FF 2003 1192 ss, p. 1230 et 1233). Les autorités de l'état civil ne sont autorisées à prononcer un tel refus que dans les cas d'abus évidents; de simples suppositions ne suffisent pas.
5.2 En l'espèce, la cour cantonale a considéré que c'est à bon droit que l'Officier de l'état civil du Nord vaudois a refusé de prêter son concours à l'enregistrement du partenariat des recourants, pour le motif que les éléments de fait font ressortir une conjonction suffisante d'indices prouvant qu'il s'agit manifestement d'un partenariat de complaisance. Selon les juges précédents, il ressort en effet du dossier et des procès-verbaux d'audition des recourants de nombreux éléments amenant à considérer comme invraisemblable le projet des partenaires de fonder une union au sens de la LPart. X._ a expressément affirmé que le but de son partenaire "n'était pas de venir en Suisse pour ne rester que trois mois" et qu'"il cherchait quand même la possibilité de travailler et s'établir en Suisse". Il a exposé qu'au vu du contact établi et compte tenu de leur "bonne collaboration et bonne amitié", ils avaient entrevu la possibilité de faire un contrat de partenariat enregistré. X._ a encore ajouté que la présence de son partenaire lui permettait "d'avoir une personne qui s'occupe de lui, qui s'occupe de son ménage et de la cuisine" et lui évite "d'appeler Police Secours en cas de malaise". Enfin, quand on lui demande où se situe l'amour dans cette relation, il déclare sans ambages: "mais je ne me marie pas, je fais un contrat de partenariat où il n'y a pas directement de l'amour mais plus de plaisir en commun". A cela s'ajoute que Y._ fait l'objet d'une procédure de renvoi à la suite du refus des autorités de police des étrangers de lui délivrer une autorisation de séjour en Suisse; les intéressés ont déposé leur demande d'enregistrement sept mois seulement après s'être connus, ce qui paraît, selon la cour cantonale, bien prématuré pour un engagement similaire à un mariage; les partenaires ont une grande différence d'âge, à savoir quarante ans, et ils ne parlent pas la même langue. Enfin, les nombreuses déclarations contradictoires des partenaires confirment l'existence d'un abus manifeste de la législation en matière de partenariat enregistré.
5.3 Invoquant pêle-mêle la violation "des principes et droits constitutionnels, tels le droit au respect de la vie privée et familiale (art. 13 Cst., 8 CEDH), le droit à l'égalité de traitement et l'interdiction de discrimination (art. 8 Cst.), de proportionnalité (art. 5 al. 2 Cst.) et de l'interdiction de l'arbitraire (art. 9 Cst.) dans l'application du droit cantonal, ainsi qu'une violation de la vie privée", les recourants exposent en substance qu'ils ont une volonté réelle de fonder un partenariat enregistré car ils sont heureux ensemble. Ils reprochent à la cour cantonale de ne pas traiter Y._, du fait qu'il est étranger, sur le même pied d'égalité que d'autres partenaires qui ne le seraient pas. Selon eux, la décision attaquée serait arbitraire et choquante dans son résultat puisqu'elle revient à leur interdire de vivre en partenariat "selon le principe de la liberté de choix et la liberté personnelle". L'arrêt entrepris ne respecterait pas non plus le principe de proportionnalité; l'Office de l'état civil préjugerait des buts de leur relation, qui serait soi-disant d'obtenir un titre de séjour pour Y._, sans même qu'il y ait eu des faits concrets qui laisseraient transparaître que ce serait le cas. Or, si tel était réellement le cas, le Service de la population pourrait révoquer l'autorisation de séjour après que le partenariat aurait été conclu.
Selon les recourants, il n'est "pas opportun que l'Officier de l'état civil ait un rôle aussi important que celui qui lui a été donné dans le cas d'espèce (comme dans d'autres cas semblables de refus d'enregistrement) dans des mesures de police, de surveillance, de contrôle, avec pouvoir sanctionnateur"; un Officier de l'état civil "se mêlant autant des mesures de police des étrangers" excéderait et abuserait de sa compétence et de son rôle.
5.4 Par cette critique, les recourants s'en prennent en réalité à l'existence même ainsi qu'au contenu de l'art. 6 LPart. Une telle critique est toutefois irrecevable, dans la mesure où l'art. 190 Cst. (auparavant art. 191 Cst.) interdit au Tribunal fédéral d'examiner la constitutionnalité des lois fédérales (ATF 131 II 562 consid. 3.2 p. 565; 130 II 65 consid. 4.2 p. 71; au sujet de l'art. 113 al. 3 aCst., ATF 126 I 1 consid. 2f p. 5; 125 III 209 consid. 5 p. 216).
Au surplus, en tant qu'ils font valoir qu'ils ont une volonté réelle de fonder un partenariat enregistré, qu'ils ne peuvent pas vivre l'un sans l'autre et qu'ils vivent dans le présent, ce qui expliquerait qu'ils ne se rappellent pas "de tous les autres détails de vie", leur argumentation ne convainc pas. Ce faisant, les recourants se bornent à substituer de façon inadmissible leur propre appréciation à celle de la cour cantonale; au surplus, en tant qu'ils s'écartent des faits constatés par les juges précédents - sans en établir l'arbitraire (cf. supra, consid. 1.3) - leur critique est irrecevable. Enfin, le renvoi aux motifs présentés devant les instances précédentes est également irrecevable; un tel renvoi n'est, en effet, pas suffisant au regard de l'art. 42 al. 1 et 2 LTF, la motivation devant être développée dans l'acte de recours (ATF 133 II 396 consid. 3.2 p. 400; 131 III 384 consid. 2.3 p. 387).
5.5 Dans son résultat, l'appréciation juridique des faits par la cour cantonale est conforme au droit fédéral. En effet, bien que les recourants semblent cohabiter, X._ a manifestement une conception erronée de l'institution juridique du partenariat lorsqu'il déclare qu'il suffit d'avoir "une bonne collaboration" et une "bonne amitié" avec l'autre, qu'il "ne se marie pas", mais fait "un contrat de partenariat où il n'y a pas directement de l'amour mais plus de plaisir en commun", qu'il a ainsi une personne qui s'occupe de lui, de son ménage et de la cuisine. Dès lors qu'il ressort de l'arrêt attaqué qu'il se considère "comme un père ou un grand-père protecteur" à l'égard de Y._ - puisqu'il n'a lui-même pas eu de fils -, qu'il a quarante ans de plus que celui-ci, qu'ils ne peuvent pas communiquer si ce n'est à l'aide du dictionnaire, que X._ n'envisage pas de faire quoi que ce soit si Y._ n'obtient pas de permis de séjour - à ce sujet, il a répondu à l'officier de l'état civil: "Rien, tant pis. A 72 ans nous sommes moins ardents qu'à 42 ans" -, les conditions d'une relation stable et exclusive dans ses composantes corporelle et spirituelle ne sont manifestement pas remplies. Quant à l'intention d'éluder les règles sur le séjour des étrangers, c'est également à juste titre que la cour cantonale l'a considérée comme manifeste; Y._ est venu en Suisse avec un visa touristique, s'est vu refuser un permis de séjour et fait l'objet d'une procédure de renvoi, décision contre laquelle il a fait recours.
6. Vu ce qui précède, le recours est rejeté dans la mesure où il est recevable. Les recourants, qui succombent, supporteront solidairement les frais judiciaires (art. 66 al. 1 et 5 LTF). L'intimée n'a pas droit à des dépens (art. 68 al. 3 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours constitutionnel est irrecevable.
2. Le recours en matière civile 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. Le présent arrêt est communiqué aux parties, à la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud, à l'Office fédéral des migrations et à l'Office fédéral de l'état civil à l'intention de l'Office fédéral de la justice.
Lausanne, le 2 février 2010
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl Aguet