Sachverhalt: A. X._ wurde 1967 in der Türkei geboren. Ab 1985 unterhielt er dort eine Beziehung mit der 1972 geborenen Z._. Im August 1986 gebar diese das erste gemeinsame Kind. Im November 1989 reiste X._ in die Schweiz ein und stellte hier ein Asylgesuch. Im Januar 1990 gebar Z._ in der Türkei das zweite gemeinsame Kind. Am 30. August 1990 wurde das Asylgesuch erstinstanzlich abgewiesen. Dagegen erhob X._ Beschwerde. Im Jahr 1993 lernte er in der Schweiz die 1944 geborene Y._ kennen und zog im Frühling 1994 in ihre Wohnung. Mit Urteil vom 20. Oktober 1994 bestätigte die Asylrekurskommission letztinstanzlich den ablehnenden Asylentscheid und setzte X._ eine Ausreisefrist bis zum 31. Januar 1995 an. Am 1. Februar 1995 verliess er die Schweiz, kehrte in sein Heimatland zurück und nahm sogleich wieder die Beziehung mit Z._ auf. Mit dieser zeugte er im März 1995 das dritte Kind. Im Frühling 1995 besuchte Y._ den X._ in der Türkei. Anlässlich eines weiteren Besuchs von Y._ in der Türkei heirateten die beiden dort am 6. Juni 1995. Aufgrund der Heirat wurde X._ im Kanton Zürich eine Aufenthaltsbewilligung erteilt. Im November 1995 zog er zu Y._ in die Schweiz. Am 1. Januar 1996 gebar Z._ in der Türkei das dritte Kind. B. Am 16. März 1999 ersuchte X._ um die erleichterte Einbürgerung. Im Rahmen des Einbürgerungsverfahrens unterzeichneten er und Y._ am 4. Mai 2000 gemeinsam eine Erklärung, wonach sie in einer tatsächlichen, ungetrennten und stabilen ehelichen Gemeinschaft an derselben Adresse zusammenlebten und weder Trennungs- noch Scheidungsabsichten hätten. Sie nahmen unterschriftlich zur Kenntnis, "dass die erleichterte Einbürgerung nicht möglich ist, wenn vor oder während des Einbürgerungsverfahrens einer der Ehegatten die Trennung oder Scheidung beantragt hat oder keine tatsächliche eheliche Gemeinschaft mehr besteht. Ebenso bestätigten sie zu wissen, dass die Verheimlichung solcher Umstände zur Nichtigerklärung der Einbürgerung führen könne. Am 13. Juni 2000 wurde X._ in Anwendung von 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. C. Im Dezember 2001 reichten X._ und Y._ gemeinsam ein Scheidungsbegehren ein. Mit Urteil vom 15. Juli 2002 schied das Bezirksgericht Uster die Ehe. Das Urteil erwuchs am 31. August 2002 in Rechtskraft. Am 19. Februar 2003 heiratete X._ in der Türkei Z._. Am 26. Mai 2003 stellte er für diese und die drei Kinder ein Gesuch um Familiennachzug. D. Mit Schreiben vom 28. November 2003 teilte das Bundesamt für Migration (im Folgenden: Bundesamt) X._ mit, es bestehe Grund zur Annahme, dass er die Einbürgerung erschlichen habe und die Voraussetzungen für deren Nichtigerklärung gemäss Art. 41 BüG erfüllt seien. Am 15. März bzw. 4. April 2005 erteilten die Heimatkantone Schwyz und Zürich die Zustimmung zur Nichtigerklärung der erleichterten Einbürgerung. Mit Verfügung vom 10. Mai 2005 erklärte das Bundesamt die erleichterte Einbürgerung von X._ als nichtig. Die von X._ hiergegen erhobene Beschwerde wies das Bundesverwaltungsgericht mit Urteil vom 29. August 2008 ab. E. X._ und Y._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, das Urteil des Bundesverwaltungsgerichts sei aufzuheben; die Nichtigerklärung der Einbürgerung sei aufzuheben und X._ das Schweizer Bürgerrecht zu belassen. In prozessualer Hinsicht beantragen sie, folgende Personen seien als Zeugen einzuvernehmen: Y._, A._, B._, C._, die Ehegatten D._, die Ehegatten E._ und F._. Überdies sei X._ zu befragen. Die Scheidungsakten des Bezirksgerichts Uster seien beizuziehen. Eventualiter sei den Beschwerdeführern Frist anzusetzen, um von den genannten Personen schriftliche Erklärungen beizuziehen. Eventualiter sei das Verfahren zur Durchführung des Beweisverfahrens an das Bundesverwaltungsgericht zurückzuweisen. F. Das Bundesamt und das Bundesverwaltungsgericht haben auf Vernehmlassung verzichtet. 