Sachverhalt: A. X._ wurde 1963 geboren und stammt ursprünglich aus der Türkei. Er reiste am 2. Oktober 1990 in die Schweiz ein und ersuchte um Asyl. Am 6. Oktober 1993 lehnte das damalige Bundesamt für Flüchtlinge (heute Bundesamt für Migration [BFM]) das Gesuch ab und wies X._ aus der Schweiz weg; es wurde ihm Frist angesetzt, das Land bis am 31. Januar 1994 zu verlassen. Am 15. Oktober 1993 heiratete X._ die im Jahr 1957 geborene Schweizer Bürgerin A._ und erhielt in der Folge eine Aufenthaltsbewilligung. Am 16. Dezember 1996 stellte er ein Gesuch um erleichterte Einbürgerung in der Schweiz. Nachdem Abklärungen ergeben hatten, dass die Eheleute seit März 1997 getrennt lebten, wurde das Einbürgerungsverfahren eingestellt. Am 21. April 1998 wurde die Ehe rechtskräftig geschieden. Am 22. Mai 1998 heiratete X._ die im Jahr 1952 geborene Schweizer Bürgerin B._. Gestützt auf diese Ehe stellte er am 29. Mai 2001 ein zweites Gesuch um erleichterte Einbürgerung. Im anschliessenden Verfahren unterzeichneten sowohl er als auch seine Ehefrau am 13. Mai 2002 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. Ebenfalls bestätigten sie ihre Kenntnisnahme davon, dass die Verheimlichung solcher Umstände zur Nichtigerklärung der Einbürgerung führen könne. Am 30. Mai 2002 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 der Kantone Luzern und Solothurn sowie dasjenige der Gemeinden Luzern und Grenchen. Nachdem die damalige Ehefrau die gemeinsame Wohnung im März/ April 2003 verlassen hatte, wurde die Ehe am 26. Januar 2004 rechtskräftig geschieden. B. Mit Schreiben vom 19. Januar 2005 teilte das Bundesamt für Migration (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 Art. 41 BüG erfüllt seien. Am 16. Juni 2005 heiratete X._ die im Jahr 1968 geborene türkische Staatsangehörige C._. Es handelt sich bei ihr um die Mutter des gemeinsamen Sohnes D._, der am 8. September 1990 geboren wurde. Am 20. Juni 2005 wurde bei der Schweizerischen Botschaft in Ankara ein Visumsgesuch für die Ehefrau und den Sohn D._ eingereicht und am 20. September 2005 stellte X._ ein Familiennachzugsgesuch für die erwähnten Personen. Nachdem die Kantone Luzern und Solothurn am 29. Mai 2007 die Zustimmung gemäss Art. 41 Abs. 1 BüG erteilt hatten, erklärte das Bundesamt die Einbürgerung von X._ mit Verfügung vom gleichen Tag für nichtig. C. In der Folge erhob X._ Beschwerde beim Bundesverwaltungsgericht und verlangte die Aufhebung der Verfügung des Bundesamts vom 29. Mai 2007. Mit Urteil vom 18. Februar 2009 wies das Bundesverwaltungsgericht das Rechtsmittel ab. Es erwog, X._ habe die erleichterte Einbürgerung durch falsche Angaben bzw. das Verheimlichen erheblicher Tatsachen im Sinne von Art. 41 BüG erschlichen. Ausserdem wies es verschiedene wegen angeblicher Verfahrensmängel erhobene Rügen ab. D. Mit Eingabe vom 2. April 2009 erhebt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 ff. BGG). Er beantragt im Wesentlichen die Aufhebung des Urteils des Bundesverwaltungsgerichts vom 18. Februar 2009 und die Feststellung der Verletzung des Beschleunigungsgebots und des rechtlichen Gehörs durch die Vorinstanzen. Er ersucht zudem um Gewährung der aufschiebenden Wirkung. Der Beschwerdeführer rügt, der angefochtene Entscheid verletzte Art. 6 EMRK, das Willkürverbot (Art. 9 BV), den Anspruch auf Behandlung innert nützlicher Frist und das Gebot der Fairness im Verfahren (Art. 29 Abs. 1 BV), den Anspruch auf rechtliches Gehör (Art. 29 Abs. 2 BV) sowie Art. 41 BüG. Zudem macht er eine unrichtige Feststellung des Sachverhalts durch die Vorinstanz geltend (Art. 97 Abs. 1 BGG). E. Mit Präsidialverfügung vom 11. Mai 2009 wurde der Beschwerde aufschiebende Wirkung zuerkannt. F. Das Bundesverwaltungsgericht hat auf eine Vernehmlassung ausdrücklich verzichtet. Vom Bundesamt ist keine Stellungnahme eingegangen. Mit Eingabe vom 19. Mai 2009 hat der Beschwerdeführer ergänzende Unterlagen eingereicht. 