Sachverhalt:
A. X._ wurde 1974 geboren und stammt ursprünglich aus Brasilien. Er hielt sich nach eigenen Angaben 1996 ferienhalber in der Schweiz auf und lernte hier die im Jahr 1971 geborene Schweizer Bürgerin Y._ kennen. Am 28. April 1997 verheiratete sich das Paar und X._ erhielt in der Folge eine Aufenthaltsbewilligung im Kanton Zürich.
Am 25. Juni 2002 stellte X._ ein Gesuch um erleichterte Einbürgerung in der Schweiz. Im Rahmen des Einbürgerungsverfahrens veranlasste das kantonal-zürcherische Amt für Gemeinden und berufliche Vorsorge, Abteilung Einbürgerungen, Abklärungen zum Leumund des Gesuchstellers und übermittelte deren Ergebnis am 21. Januar 2003 mit einer negativen Stellungnahme dem Bundesamt für Migration (BFM). Letzteres holte im Februar 2003 diverse Referenzen ein.
Am 27. März 2003 unterzeichnete sowohl X._ als auch seine Ehefrau die Erklärung, wonach sie in einer tatsächlichen, ungetrennten, stabilen ehelichen Gemeinschaft an derselben Adresse zusammenlebten und dass weder Trennungs- noch Scheidungsabsichten bestünden. Gleichzeitig nahmen sie unterschriftlich zur Kenntnis, dass eine erleichterte Einbürgerung nicht möglich sei, wenn vor oder während des Einbürgerungsverfahrens einer der Ehegatten die Trennung oder Scheidung beantrage oder keine tatsächliche eheliche Gemeinschaft mehr bestehe. Ebenso bestätigten sie ihre Kenntnisnahme davon, dass die Verheimlichung solcher Umstände zur Nichtigerklärung der Einbürgerung führen könne.
Am 19. Mai 2003 wurde X._ gestützt auf Art. 27 des Bundesgesetzes vom 29. September 1952 über Erwerb und Verlust des Schweizer Bürgerrechts (Bürgerrechtsgesetz [BüG]; SR 141.0) erleichtert eingebürgert. Mit dem Schweizer Bürgerrecht erwarb er auch das Bürgerrecht des Kantons Zürich sowie dasjenige der Gemeinde Buchs (ZH).
Am 30. März 2004 gelangten X._ und seine Ehefrau an das Bezirksgericht Zürich und ersuchten in einem gemeinsamen Begehren um Scheidung. Mit Urteil des Bezirksgerichts Zürich vom 27. August 2004 wurde die Ehe geschieden.
B. Mit Schreiben vom 24. Oktober 2005 teilte das BFM X._ mit, er habe kurz vor seiner Einbürgerung zusammen mit seiner Ehefrau schriftlich bestätigt, in einer stabilen ehelichen Gemeinschaft zu leben. Trotzdem sei die Ehe in der Zwischenzeit bereits aufgelöst worden. Es bestehe daher Grund zur Annahme, dass er die Einbürgerung durch falsche Angaben erschlichen habe und dass die Voraussetzungen für eine Nichtigerklärung nach <ref-law> erfüllt seien. Im Verlauf des vom Bundesamt eingeleiteten Verfahrens betreffend Nichtigerklärung der Einbürgerung konnte X._ mehrmals schriftlich Stellung nehmen. Nachdem der Kanton Zürich am 18. April 2008 die Zustimmung gemäss <ref-law> erteilt hatte, erklärte das Bundesamt die Einbürgerung von X._ mit Verfügung vom 9. Mai 2008 für nichtig.
C. In der Folge erhob X._ Beschwerde beim Bundesverwaltungsgericht und verlangte die Aufhebung der Verfügung des Bundesamts vom 9. Mai 2008. Mit Urteil vom 8. Juni 2009 wies das Bundesverwaltungsgericht das Rechtsmittel ab. Es erwog, X._ habe die Behörden über eine wesentliche Tatsache getäuscht und die erleichterte Einbürgerung somit im Sinne von <ref-law> erschlichen. Die Voraussetzungen für eine Nichtigerklärung der erleichterten Einbürgerung seien deshalb erfüllt. Die Vorinstanz verneinte ausserdem das Vorliegen angeblicher Verfahrensmängel.
D. Mit Eingabe vom 13. Juli 2009 erhebt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>). Er beantragt die Aufhebung des Urteils des Bundesverwaltungsgerichts vom 8. Juni 2009 und der Verfügung des Bundesamts für Migra-tion vom 9. Mai 2008. Weiter verlangt er die Einstellung des Verfahrens betreffend Nichtigerklärung der erleichterten Einbürgerung und er ersucht um Gewährung der aufschiebenden Wirkung. Der Beschwerdeführer rügt, der angefochtene Entscheid verletzte das Willkürverbot (<ref-law>) und den Anspruch auf rechtliches Gehör (<ref-law>).
E. Mit Präsidialverfügung vom 18. August 2009 wurde der Beschwerde aufschiebende Wirkung zuerkannt.
F. Das Bundesamt beantragt in seiner Stellungnahme Abweisung der Beschwerde, ohne dass es sich inhaltlich nochmals zur Angelegenheit äussert. Das Bundesverwaltungsgericht verzichtet auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Das angefochtene Urteil ist ein Endentscheid des Bundesverwaltungsgerichts (Art. 86 Abs. 1 lit. a, Art. 90 BGG). Ihm liegt ein Beschwerdeverfahren über eine Nichtigerklärung einer erleichterten Einbürgerung und damit eine öffentlich-rechtliche Angelegenheit zugrunde. Die Ausnahme der ordentlichen Einbürgerung gemäss <ref-law> erstreckt sich nicht auf die Nichtigerklärung der Einbürgerung. Auch die übrigen Sachurteilsvoraussetzungen sind erfüllt und geben zu keinen weiteren Bemerkungen Anlass. Auf die Beschwerde ist grundsätzlich einzutreten.
1.2 Nicht einzutreten ist auf die Rechtsbegehren des Beschwerdeführers, wonach auch die Verfügung des Bundesamts für Migration vom 9. Mai 2008 aufzuheben und das Verfahren betreffend Nichtigerklärung der erleichterten Einbürgerung des Beschwerdeführers einzustellen sei. Nach dem Prinzip des Devolutiveffekts geht die Zuständigkeit zum Entscheid über eine angefochtene Verfügung grundsätzlich an die Beschwerdeinstanz über; mit der Einreichung einer Beschwerde wird der Verwaltung mit andern Worten die Herrschaft über den Streitgegenstand, insbesondere auch in Bezug auf die tatsächlichen Verfügungs- und Entscheidungsgrundlagen, grundsätzlich entzogen (vgl. <ref-ruling> E. 4.2 S. 142 f. mit Hinweisen). Der Devolutiveffekt bewirkt zudem, dass der Entscheid des BFM durch das Urteil des Bundesverwaltungsgerichts vom 8. Juni 2009 ersetzt worden ist und als inhaltlich mitangefochten gilt (vgl. <ref-ruling> E. 1 S. 441; <ref-ruling> E. 1c S. 33; je mit Hinweisen).
1.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 97 Abs. 1 bzw. <ref-law>). Eine entsprechende Rüge setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
2. 2.1 Der Beschwerdeführer rügt, er habe erst der Verfügung des BFM vom 9. Mai 2008 entnehmen können, dass der Kanton Zürich die nach <ref-law> erforderliche Zustimmungserklärung erteilt habe. Ein entsprechendes Schriftstück sei ihm indessen bis heute nicht zur Kenntnis gebracht und die kantonale Zustimmungserklärung sei ihm gegenüber nie eröffnet worden. Diese Zustimmungserklärung stelle eine Verfügung dar und da Verfügungen, die dem Betroffenen nicht eröffnet werden, keine Rechtswirkungen entfalten können, fehle es vorliegend an einer notwendigen Voraussetzung für die Nichtigerklärung der Einbürgerung. Schon aus diesem Grund müsse die Verfügung des BFM vom 9. Mai 2008 aufgehoben werden.
2.2 Gemäss <ref-law> kann die Einbürgerung vom Bundesamt mit Zustimmung der Behörde des Heimatkantons innert fünf Jahren nichtig erklärt werden, wenn sie durch falsche Angaben oder Verheimlichung erheblicher Tatsachen erschlichen worden ist. Nach dieser Bestimmung stellt die kantonale Zustimmungserklärung eine notwendige, nicht aber hinreichende Voraussetzung für die Nichtigerklärung einer Einbürgerung dar. Das Bundesamt muss nach <ref-law> zusätzlich prüfen, ob auch die materiellrechtlichen Voraussetzungen der Nichtigerklärung erfüllt sind (Erschleichen der Einbürgerung durch falsche Angaben oder Verheimlichung erheblicher Tatsachen). Im Verhältnis zum Betroffenen wirkt deshalb erst die Verfügung des Bundesamts rechtsgestaltend, wobei sich dieser Entscheid wie dargelegt nicht allein auf die kantonale Zustimmungserklärung abstützen darf. Die Zustimmungserklärung vermag für sich allein somit keine Nichtigerklärung der Einbürgerung zu bewirken, weshalb sie nicht als Verfügung qualifiziert werden kann. Gemäss <ref-law> (SR 172.021) gelten als Verfügungen Anordnungen der Behörden im Einzelfall, die u.a. die Begründung, Änderung oder Aufhebung von Rechten und Pflichten zum Gegenstand haben. Gilt die kantonale Zustimmungserklärung gemäss <ref-law> nicht als Verfügung, waren die Behörden nicht verpflichtet, diese dem Beschwerdeführer zu eröffnen. Die Beschwerde erweist sich daher in diesem Punkt als unbegründet. Damit sind aber auch die sinngemässen Rügen nicht zu hören, der Kanton sei bei Abgabe seiner Zustimmungserklärung unzureichend informiert gewesen, habe sich mit den Argumenten den Beschwerdeführers nicht ernsthaft auseinander gesetzt und daher dessen rechtliches Gehör verletzt.
2.3 Mit dem Hinweis, er habe von der kantonalen Zustimmungserklärung angeblich bis anhin keine Kenntnis nehmen können, vermag der Beschwerdeführer keine Rechtsverletzung darzutun. Vom Vorliegen dieser Erklärung wusste er spätestens seit der Zustellung der Verfügung des BFM vom 9. Mai 2008, weil hier ausdrücklich darauf hingewiesen wird. Dass ihm danach die Akteneinsicht verweigert worden wäre, macht er nicht geltend. Auf dieses Vorbringen ist daher nicht weiter einzugehen.
3. 3.1 Der Beschwerdeführer rügt ausserdem, indem die Vorinstanz seinen Antrag auf Befragung der Ex-Ehefrau abgelehnt und von dieser nicht einmal eine schriftliche Auskunft eingeholt habe, habe sie seinen Anspruch auf rechtliches Gehör verletzt. Die Begründung der Ablehnung des Antrags mit dem Hinweis, beide Ehegatten gingen der Prostitution nach und es sei deshalb unglaubwürdig, dass die zuvor angeblich intakte Beziehung in der vom Beschwerdeführer dargestellten Weise an einer Drittbeziehung gescheitert sei, sei diskriminierend. Die Vorinstanz spreche damit einer Person, die der Prostitution nachgehe, generell die Fähigkeit ab, eine Liebesbeziehung einzugehen. Für seine Frau habe er starke Gefühle gehabt, die nicht durch die rein sexuellen gewerblichen Dienstleistungen, die sie für ihre Kunden erbracht habe, sondern erst durch die Eingehung einer eigentlichen Beziehung zu einem anderen Mann gestört worden seien. Er sei zudem bisexuell veranlagt, weshalb in keiner Weise ausgeschlossen sei, dass er mit seiner Ehefrau eine Geschlechtsgemeinschaft unterhalten habe. Der Beschwerdeführer macht geltend, eine Befragung der damaligen Ehefrau hätte ergeben, dass zwischen ihnen eine echte Ehe bestanden habe, dass diese Ehe im Zeitpunkt der Einbürgerung noch völlig intakt gewesen und erst zu einem späteren Zeitpunkt an der erwähnten Fremdbeziehung der Ehefrau gescheitert sei.
3.2 Der Anspruch auf rechtliches Gehör nach <ref-law> umfasst auch das Recht, Beweisanträge zu stellen und - als Korrelat dazu - die Pflicht der Behörde zur Beweisabnahme. Beweise sind im Rahmen dieses verfassungsmässigen Anspruchs jedoch nur über jene Tatsachen abzunehmen, die für die Entscheidung der Streitsache erheblich sind. Die Verfassungsgarantie steht zudem einer vorweggenommenen Beweiswürdigung nicht entgegen. Das Gericht kann deshalb auf die Abnahme von Beweisen verzichten, wenn es aufgrund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, seine Überzeugung werde durch weitere Beweiserhebungen nicht geändert (<ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 3 S. 157 mit Hinweisen).
3.3 Das Bundesgericht kann die Verletzung von verfassungsmässigen Rechten nur insofern prüfen, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 2 S. 639 f.). Das bedeutet, dass - entsprechend den altrechtlichen Begründungsanforderungen von Art. 90 Abs. 1 lit. b OG - klar und detailliert anhand der Erwägungen des angefochtenen Entscheids darzulegen ist, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-ruling> E. 6 S. 397). Bei einer Anrufung des Willkürverbots muss dargetan werden, dass und inwiefern der angefochtene Entscheid offensichtlich unhaltbar sein soll, d.h. mit der tatsächlichen Situation in klarem Widerspruch stehe, auf einem offenkundigen Versehen beruhe oder sich sachlich in keiner Weise rechtfertigen lasse (<ref-ruling> E. 3.2 S. 400; <ref-ruling> E. 7.1 S. 398). Auf rein appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling> E. 2 S. 591 f.).
3.4 Die Vorinstanz erwog, anlässlich der scheidungsrichterlichen Einvernahme habe der Beschwerdeführer am 27. Mai 2004 erklärt, den Trennungsentschluss schon vor längerer Zeit getroffen zu haben. Gegen seine Darstellung, dass erst eine angebliche Fremdbeziehung der Ehefrau zum Scheitern der Ehe geführt habe, spreche zudem, dass er nicht in der Lage gewesen sei, Angaben zum angeblichen Ehestörer zu machen. Auch habe er nichts unternommen, um die angeblich eben noch intakte Ehe zu retten. Gestützt auf diese Erwägungen gelangte die Vorinstanz zum Schluss, dass zusätzliche Abklärungen zu keinen neuen Erkenntnissen führen würden. Sie befand, aufgrund der Aktenlage könne nachgewiesen werden, dass die Vorbringen des Beschwerdeführers bezüglich des Scheiterns seiner Ehe wegen einer angeblichen Fremdbeziehung der Ehefrau nicht zutreffend sein können. Auf die Befragung der Schweizer Ehefrau und des angeblichen Ehestörers könne daher verzichtet werden.
3.5 Die Vorinstanz hat den Verzicht auf die beantragte Befragung der Schweizer Ehefrau und ihres angeblichen Freundes mit dem Hinweis auf die Aktenlage begründet. Gestützt darauf stehe fest, dass die Vorbringen des Beschwerdeführers insbesondere bezüglich der angeblichen Fremdbeziehung der Ehefrau nicht zutreffend sein können; die beantragten Befragungen seien deshalb nicht geeignet, zu neuen Erkenntnissen zu führen. Die Vorinstanz hat den Beweisantrag des Beschwerdeführers mithin gewürdigt, wenn auch antizipiert. Die Rüge der Gehörsverletzung ist somit unbegründet. Zu prüfen bleibt, ob diese antizipierte Beweiswürdigung willkürlich ist.
Der Beschwerdeführer vermag nicht darzutun, dass die von der Vorinstanz in diesem Zusammenhang vorgenommenen Erwägungen unhaltbar seien. Bezüglich der Annahme der Vorinstanz, es sei davon auszugehen, dass der Beschwerdeführer im Mai 2004 den Trennungsentschluss schon vor längerer Zeit getroffen habe, macht er keine hinreichend substanziierten Vorbringen, die diese als offensichtlich unhaltbar erscheinen liessen. Zudem substanziiert er auch nicht vor Bundesgericht seine Ausführungen zum angeblichen Ehestörer und er stellt weiterhin nicht in Abrede, dass er nichts unternommen habe, um die angeblich eben noch intakte Ehe zu retten.
Die Ausführungen des Beschwerdeführers zu den angeblichen Erwägungen der Vorinstanz, dass beide Ehegatten der Prostitution nachgegangen seien, und es deshalb unglaubwürdig sei, dass die zuvor intakte Beziehung in der vom Beschwerdeführer dargestellten Weise an einer Dirittbeziehung gescheitert sei, sind weitgehend unzulässig. Jedenfalls vermag er damit nicht darzutun, dass die Vorinstanz die antizipierte Beweiswürdigung auf eine unhaltbare Begründung abgestützt hätte, d.h. auf eine Begründung, die mit der tatsächlichen Situation in klarem Widerspruch steht, auf einem offenkundigen Versehen beruht oder sich sachlich in keiner Weise rechtfertigen lässt. Praxisgemäss tritt das Bundesgericht zudem insoweit nicht auf Ausführungen ein, als damit auf Ausführungen vor Vorinstanzen verwiesen wird (<ref-ruling> E. 3.1 S. 399 f.). Soweit der Beschwerdeführer geltend macht, die Argumentation der Vorinstanz sei diskriminierend, denn sie spreche einer Person, die der Prostitution nachgehe, generell die Fähigkeit ab, eine Liebesbeziehung einzugehen, übt er weitgehend appellatorische Kritik am angefochtenen Entscheid. Sodann ist sein Vorbringen, er habe für seine Frau starke Gefühle gehabt, die durch deren Tätigkeit als Prostituierte nicht gestört worden seien, ungenügend substanziiert und vermag daher die diesbezügliche Feststellung der Vorinstanz nicht zu entkräften: Die Vorinstanz hielt fest, die blosse Beteuerung des Beschwerdeführers, die Tätigkeit seiner Ehefrau toleriert zu haben und ansonsten an sie emotional gebunden gewesen zu sein, genüge nicht, um die Tatsachenvermutung für das Fehlen einer ehelichen Gemeinschaft infrage zu stellen. Schliesslich ist auch nicht auf das Vorbringen des Beschwerdeführers weiter einzugehen, er sei bisexuell veranlagt, weshalb es nicht ausgeschlossen sei, dass er eine Geschlechtsgemeinschaft mit seiner Ehefrau unterhalte. Mit dieser Behauptung nimmt er Bezug auf die Feststellung der Vorinstanz, die homosexuelle Ausrichtung des Beschwerdeführers, der seit 2005 mit seinem homosexuellen Freund zusammenwohne, stelle ein weiteres Indiz dafür dar, dass er und seine Ehefrau keine Ehe im Sinne einer ungeteilten Geschlechtsgemeinschaft zwischen Mann und Frau geführt hätten. Angesichts der fehlenden Substanziierung erscheint das Vorbringen als reine Schutzbehauptung, zumal es vom Beschwerdeführer erstmals vor Bundesgericht vorgetragen wird.
Somit ergibt sich, dass der Beschwerdeführer gegen die Begründung des Beweisabnahmeverzichts durch die Vorinstanz nichts vorzubringen vermag, was diese als unhaltbar erscheinen liesse, soweit auf seine entsprechenden Vorbringen überhaupt einzutreten ist. Die von der Vorinstanz vorgenommene antizipierte Beweiswürdigung ist deshalb verfassungsrechtlich nicht zu beanstanden.
4. Gegen die Sachverhaltsfeststellung der Vorinstanz erhebt der Beschwerdeführer keine weiteren Rügen und diese ist auch nicht offensichtlich unrichtig (<ref-law>). Damit bleibt es bei der tatsächlichen Vermutung, dass die Ehe im Zeitpunkt der Gesuchseinreichung und Einbürgerung nicht tatsächlich gelebt wurde, welche Vermutung die Vorinstanz im Wesentlichen auf folgende Umstände stützte: Der Beschwerdeführer hat sich im homosexuellen Umfeld gewerbsmässig prostituiert, aber auch seine Schweizer Ehefrau war als Prostituierte tätig. Zwischen der erleichterten Einbürgerung (19. Mai 2003) und der Aufgabe des Ehewillens (Einreichung des gemeinsamen Scheidungsbegehrens am 30. März 2004) lag eine vergleichsweise kurze Zeitspanne von lediglich zehn Monaten. Anlässlich der scheidungsrichterlichen Einvernahme vom 27. Mai 2004 erklärte der Beschwerdeführer zudem, den Trennungsentschluss schon vor längerer Zeit getroffen zu haben. Zur angeblichen Fremdbeziehung der Ehefrau machte er keine substanziierten Ausführungen und er brachte auch nicht vor, irgendwelche Bemühungen zur Rettung der Ehe unternommen zu haben. Bei dieser Sachlage erweist sich die Schlussfolgerung der Vorinstanz, dass der Beschwerdeführer sie getäuscht und die erleichterte Einbürgerung im Sinne von <ref-law> somit erschlichen habe, als bundesrechtskonform (vgl. <ref-ruling> E. 2 u. 3 S. 164 ff.).
5. Die Beschwerde ist daher abzuweisen, soweit darauf einzutreten ist.
Dem Ausgang des vorliegenden Verfahrens entsprechend sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Eine Parteientschädigung ist nicht zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird dem Beschwerdeführer, dem Bundesamt für Migration und dem Bundesverwaltungsgericht, Abteilung III, schriftlich mitgeteilt.
Lausanne, 16. November 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Kappeler