Sachverhalt:
A. X._ wurde 1959 in Mazedonien geboren. 1984 heiratete er dort die mazedonische Staatsangehörige A._. Aus der Ehe sind die Kinder B._ und C._ hervorgegangen. Am 24. Oktober 1996 liessen sich die Ehegatten scheiden. Die Kinder wurden der Mutter zugeteilt.
In den Jahren 1993 bis 1996 hielt sich X._ jeweils mit einer Saisonnierbewilligung in der Schweiz auf. Am 6. Dezember 1996, wenige Wochen nach der Scheidung seiner ersten Ehe, heiratete er die Schweizer Bürgerin D._. Gestützt darauf erhielt er eine Aufenthaltsbewilligung.
Am 9. November 1999 stellte X._ ein Gesuch um erleichterte Einbürgerung. Im Einbürgerungsverfahren unterzeichneten er und seine Ehefrau am 7. Juli 2000 eine Erklärung, wonach sie in stabiler ehelicher Gemeinschaft zusammenlebten und weder Trennungs- noch Scheidungsabsichten bestünden. Gleichzeitig nahmen sie zur Kenntnis, dass die erleichterte Einbürgerung nicht möglich sei, wenn vor oder während des Einbürgerungsverfahrens einer der Ehegatten die Trennung oder Scheidung beantragt habe oder keine tatsächliche eheliche Gemeinschaft mehr bestehe. Am 21. September 2000 wurde X._ das Schweizer Bürgerrecht verliehen.
Die elterliche Sorge über die zwei Kinder aus der ersten Ehe wurde 1999 auf X._ übertragen. Die Kinder reisten am 7. Februar 2001 in die Schweiz ein und erhielten eine Aufenthaltsbewilligung. Die Ehe von X._ mit seiner Schweizer Ehefrau wurde am 19. Februar 2002 geschieden. Am 21. März 2002 reiste seine geschiedene erste Ehefrau rechtswidrig in die Schweiz ein, und am 3. Mai 2002 heirateten die beiden erneut.
Mit Schreiben vom 20. Mai 2003 orientierte das Bundesamt für Zuwanderung, Integration und Auswanderung (IMES, heute: Bundesamt für Migration, BFM) X._ über die Eröffnung eines Verfahrens auf Nichtigerklärung der erleichterten Einbürgerung nach Art. 41 des Bürgerrechtsgesetzes vom 29. September 1952 (BüG; SR 141.0). X._ erhielt Gelegenheit zur Stellungnahme. Mit Verfügung vom 16. September 2005 erklärte das BFM die erleichterte Einbürgerung für nichtig.
X._ focht diese Verfügung an. Mit Urteil vom 19. Dezember 2008 wies das Bundesverwaltungsgericht die Beschwerde ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 11. Februar 2009 beantragt X._ im Wesentlichen, das Urteil des Bundesverwaltungsgerichts und die Verfügung des BFM seien aufzuheben. Es sei festzustellen, dass er die erleichterte Einbürgerung nicht durch falsche Angaben oder Verheimlichung von erheblichen Tatsachen erschlichen habe.
Das Bundesverwaltungsgericht und das BFM verzichten auf eine Vernehmlassung in der Sache. Mit Präsidialverfügung vom 9. März 2009 wurde der Beschwerde im bundesgerichtlichen Verfahren die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Die Beschwerde richtet sich gegen einen Entscheid in öffentlich-rechtlichen Angelegenheiten des Bundesverwaltungsgerichts (Art. 82 lit. a, Art. 86 Abs. 1 lit. a BGG). Die Ausnahme der ordentlichen Einbürgerungen nach <ref-law> erstreckt sich nicht auf die Nichtigerklärung der Einbürgerung. Es liegt auch keine der übrigen Ausnahmen von <ref-law> vor.
Der Beschwerdeführer beantragt, es sei festzustellen, dass er die erleichterte Einbürgerung nicht durch falsche Angaben oder die Verheimlichung von erheblichen Tatsachen erschlichen habe. Ein über die Aufhebung des angefochtenen Entscheids hinausgehendes Interesse an einer derartigen positiven Feststellung ist jedoch zu verneinen. Auf das Feststellungsbegehren ist nicht einzutreten (<ref-ruling> E. 1c S. 491 mit Hinweis; Urteil 1C_302/2008 vom 18. März 2009 E. 1.1).
Unzulässig ist auch der Antrag des Beschwerdeführers, die Verfügung des BFM vom 16. September 2005 sei aufzuheben. Diese ist durch das Urteil des Bundesverwaltungsgerichts vom 19. Dezember 2008 ersetzt worden (Devolutiveffekt) und gilt als inhaltlich mitangefochten (<ref-ruling> E. 1.4 mit Hinweis).
Im Übrigen sind die Sachurteilsvoraussetzungen erfüllt, vorbehältlich genügend begründeter Rügen (Art. 42 Abs. 2 und 106 Abs. 2 BGG).
1.2 Der Beschwerdeführer schildert den Sachverhalt aus eigener Sicht. Insoweit er damit nicht Rügen gegenüber der Sachverhaltsfeststellung der Vorinstanz verbindet (<ref-law>), besteht kein Anlass, von dieser abzuweichen (Art. 105 Abs. 1 und 2 BGG). Dies trifft insbesondere auf die Ausführungen zu den widersprüchlichen Aussagen der beiden Kinder hinsichtlich des Kontakts zu ihrer Mutter zu. Der Beschwerdeführer erklärt die Widersprüche mit einer unzulänglichen Übersetzung während der Einvernahme und mit einem Missverständnis. Er legt jedoch nicht dar, weshalb diesbezüglich die Feststellung des Sachverhalts durch das Bundesverwaltungsgericht offensichtlich unrichtig sein oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen soll (<ref-law>). Darauf ist nicht einzutreten.
2. 2.1 Der Beschwerdeführer macht geltend, die Voraussetzungen der Nichtigerklärung der erleichterten Einbürgerung nach <ref-law> seien nicht erfüllt, und rügt in diesem Zusammenhang eine Verletzung des Anspruchs auf rechtliches Gehör nach <ref-law>.
2.2 Gemäss konstanter Praxis muss im Verfahren der erleichterten Einbürgerung sowohl im Zeitpunkt der Gesuchseinreichung als auch im Zeitpunkt des Einbürgerungsentscheids eine tatsächliche Lebensgemeinschaft bestehen, die Gewähr für die Stabilität der Ehe bietet. Zweifel bezüglich eines dahin gehenden Willens sind angebracht, wenn kurze Zeit nach der erleichterten Einbürgerung die Trennung erfolgt oder die Scheidung eingeleitet wird (<ref-ruling> E. 2 S. 483 f. mit Hinweisen).
Bei der Nichtigerklärung einer erleichterten Einbürgerung ist von der Behörde zu untersuchen, ob die Ehe im massgeblichen Zeitpunkt der Gesuchseinreichung und der Einbürgerung tatsächlich gelebt wurde (vgl. <ref-law> [SR 172.021]). Im Wesentlichen geht es dabei um innere Vorgänge, die der Behörde oft nicht bekannt und schwierig zu beweisen sind. Sie kann sich daher veranlasst sehen, von bekannten Tatsachen (Vermutungsbasis) auf unbekannte (Vermutungsfolge) zu schliessen. Es handelt sich dabei um Wahrscheinlichkeitsfolgerungen, die aufgrund der Lebenserfahrung gezogen werden. Der Betroffene ist bei der Sachverhaltsabklärung mitwirkungspflichtig (<ref-ruling> E. 3.2 S. 115 f. mit Hinweisen).
Begründet die kurze Zeitspanne zwischen der erleichterten Einbürgerung einerseits und der Trennung oder Einleitung einer Scheidung andererseits die tatsächliche Vermutung, es habe schon bei der Einbürgerung keine stabile eheliche Gemeinschaft mehr bestanden, so muss der Betroffene nicht das Gegenteil beweisen. Es genügt, wenn er einen Grund anführt, der es als wahrscheinlich erscheinen lässt, dass er bei der Erklärung, wonach er mit seinem Schweizer Ehepartner in einer stabilen ehelichen Gemeinschaft lebt, nicht gelogen hat. Bei diesem Grund kann es sich um ein ausserordentliches, nach der erleichterten Einbürgerung eingetretenes Ereignis handeln, welches zum raschen Scheitern der Ehe führte, oder um das fehlende Bewusstsein des Gesuchstellers bezüglich bestehender Eheprobleme im Zeitpunkt der Einbürgerung (Urteile des Bundesgerichts 1C_294/2007 vom 30. November 2007 E. 3.6; 5A.22/2006 vom 13. Juli 2006 E. 2.3; zur Publ. bestimmtes Urteil 1C_190/2008 vom 29. Januar 2009 E. 3).
2.3 Die Vorinstanz legt dar, dass namentlich die kurze zeitliche Distanz zwischen dem Einbürgerungsverfahren und dem Scheidungsverfahren die tatsächliche Vermutung begründe, dass der Beschwerdeführer zum Zeitpunkt der gemeinsamen Erklärung vom 7. Juli 2000 nicht mehr in einer stabilen ehelichen Gemeinschaft lebte.
Der Beschwerdeführer machte demgegenüber im vorinstanzlichen Verfahren geltend, es sei ein ausserordentliches, nach der erleichterten Einbürgerung eingetretenes Ereignis gewesen, welches zum Scheitern der Ehe geführt habe, nämlich der Nachzug seiner beiden Kinder am 7. Februar 2001. Seine damalige Schweizer Ehefrau habe den Anstoss dazu gegeben, da sie selbst keine Kinder habe bekommen können, jedoch einen starken Kinderwunsch gehegt habe. Sie leide seit 1997 an Weichteilrheuma und habe infolge der Verschlimmerung der Krankheit im Jahr 2000 ihre Arbeitsstelle aufgeben müssen. Wegen der Krankheit seien gelegentlich Spannungen aufgetreten, doch sei die Ehe stabil gewesen und harmonisch verlaufen. Als die Kinder eingereist seien, sei es ihr gesundheitlich schlecht gegangen. Als sich dann auch noch die Beziehung zu den Kindern schwierig gestaltet habe, sei ihr alles zu viel geworden. Sie habe die eheliche Wohnung verlassen und sich später, nach reiflicher Überlegung, zur Scheidung entschlossen.
Die Vorinstanz bewertet diese Darstellung der Ereignisse als nicht plausibel. Sie hält es für unwahrscheinlich, dass eine zuvor harmonische Ehe mit einer Ehepartnerin, die den Nachzug der Kinder wegen eines nicht erfüllbaren eigenen Kinderwunsches initiierte, gerade wegen der Kinder innerhalb so kurzer Zeit scheiterte. Nach nur rund zwei Monaten habe der Beschwerdeführer die Vorladung zur Versöhnungsverhandlung erhalten. Die gesundheitlichen Probleme hätten schon seit mehreren Jahren bestanden. Die ersten Schritte für den Kindernachzug seien mit der Übertragung des Sorgerechts auf den Beschwerdeführer im Jahr 1999 eingeleitet worden. Es hätte deshalb Anlass und Gelegenheit bestanden, sich über mögliche Auswirkungen des Kindernachzugs auf die Gesundheit der Ehefrau Rechenschaft zu geben und entsprechende Vorbereitungen zu treffen. Selbst wenn die schweizerische Ehefrau von den Problemen im Verhältnis zu den Kindern völlig überrascht worden wäre, hätte man angesichts der angeblich harmonischen Ehe und des starken Kinderwunsches erwarten müssen, dass sie die eheliche Beziehung nicht dermassen rasch aufgebe. Für einen starken Kinderwunsch bestünden im Übrigen keine Anzeichen. Die schweizerische Ehefrau habe zwar angegeben, sie hätte den Kindernachzug angeregt. Im Übrigen habe sie kein besonderes Interesse an den Kindern erkennen lassen, zumal sie zum Beispiel nicht gewusst habe, wie alt diese im Zeitpunkt des Nachzugs gewesen seien. Aus dem Protokoll der Einvernahme vom 25. Februar 2003 gehe schliesslich hervor, dass sie ausschliesslich die Krankheit für das Scheitern der Ehe verantwortlich machte. Auch gebe es Ungereimtheiten in den Aussagen der Familienangehörigen des Beschwerdeführers, welche an dessen Sachverhaltsdarstellung generelle Zweifel weckten.
2.4 Ausgehend von diesen Erwägungen des Bundesverwaltungsgerichts sieht der Beschwerdeführer seinen Anspruch auf rechtliches Gehör in dreierlei Hinsicht als verletzt an.
Zum einen habe seine schweizerische Ehefrau ihm gegenüber den Wunsch, er solle seine Kinder zu sich in die Schweiz holen, erst im Jahr 2000 geäussert. Die Vorinstanz sei diesbezüglich von einer falschen Annahme ausgegangen. Das hätte vermieden werden können, wenn seinem Antrag, sie als Zeugin einzuvernehmen, stattgegeben worden wäre.
Die Aussage seiner schweizerischen Ehefrau anlässlich der Einvernahme vom 25. Februar 2003, der Druck sei gegen Schluss zu gross geworden und sie habe sich gefragt, warum sie zusammen bleiben sollten, könne man sodann statt auf die Krankheit ebensogut auch auf die Kinder beziehen. Dass ihr Kinderwunsch in dem Protokoll keinen augenfälligen Niederschlag gefunden habe, sei zudem nicht weiter verwunderlich, da sie gar nicht danach gefragt worden sei. Um diese beiden Fragen zu klären, hätte man sie als Zeugin befragen müssen.
Schliesslich könnten auch die erwähnten Ungereimtheiten in den Aussagen seiner Familienangehörigen ausgeräumt werden. Entgegen eines entsprechenden amtlichen Vermerks auf einem Visumsgesuch hätten nicht seine mazedonische Ehefrau, sondern die Tante und der Grossvater der Kinder diese zur Schweizer Botschaft in Skopje begleitet. Dies hätte durch die beantragte Zeugeneinvernahme der Tante und des Grossvaters bestätigt werden können.
Schliesslich könnten auch die erwähnten Ungereimtheiten in den Aussagen seiner Familienangehörigen ausgeräumt werden. Entgegen eines entsprechenden amtlichen Vermerks auf einem Visumsgesuch hätten nicht seine mazedonische Ehefrau, sondern die Tante und der Grossvater der Kinder diese zur Schweizer Botschaft in Skopje begleitet. Dies hätte durch die beantragte Zeugeneinvernahme der Tante und des Grossvaters bestätigt werden können.
2.5 2.5.1 Der aus dem Anspruch auf rechtliches Gehör (<ref-law>) abgeleitete Anspruch auf Abnahme rechtserheblicher Beweise ist nicht absolut und schliesst die antizipierte Beweiswürdigung nicht aus. Keine Verletzung des rechtlichen Gehörs liegt deshalb vor, wenn ein Gericht auf die Abnahme beantragter Beweismittel verzichtet, weil es aufgrund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und ohne Willkür annehmen kann, dass diese durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 3 S. 157; <ref-ruling> E. 4a S. 211; je mit Hinweisen).
2.5.2 Auch wenn die Darstellung des Beschwerdeführers zutreffen sollte, dass nicht schon im Jahr 1999 (mit der Übertragung des Sorgerechts), sondern erst im Jahr 2000 (mit der Äusserung eines entsprechenden Wunsches durch die schweizerische Ehefrau) der erste Schritt zum Nachzug der Kinder unternommen wurde, würde dies im Ergebnis nichts ändern. Der Beschwerdeführer scheint aufzeigen zu wollen, dass er aus Rücksicht auf die Krankheit der damaligen Ehefrau schnell habe handeln müssen, wobei nicht klar wird, wann im Jahr 2000 der besagte Wunsch geäussert worden sein soll. Das Vorbringen kann jedoch von vornherein nicht erklären, weshalb eine zuvor angeblich harmonische Ehe mit einer Ehepartnerin, die den Nachzug der Kinder wegen eines nicht erfüllbaren eigenen Kinderwunsches initiierte, gerade wegen der Kinder innerhalb so kurzer Zeit scheiterte. Zudem leuchtet nicht ein, weshalb die Rücksicht auf die Krankheit ein schnelles Handeln erforderte. Vielmehr wäre deswegen ein umsichtigeres Vorgehen angezeigt gewesen.
Eine zusätzliche Befragung der damaligen Ehefrau zur Klärung der Frage, wann der Nachzug der Kinder erstmals thematisiert wurde, war entbehrlich. Die Vorinstanz verletzte <ref-law> nicht, indem sie davon absah.
2.5.3 Ebensowenig ist ersichtlich, weshalb eine zusätzliche Einvernahme der schweizerischen Ehefrau über ihren damaligen Wunsch nach Zuzug der Kinder und über ihre Ansicht bezüglich der Gründe für das Scheitern der Ehe an der Beweislage etwas hätte ändern können. In der Einvernahme vom 25. Februar 2003 bestätigte sie, den Beschwerdeführer dazu angeregt zu haben, die Kinder zu sich in die Schweiz zu nehmen. Dies geht so auch aus dem vorinstanzlichen Entscheid hervor. Weiter stellte das Bundesverwaltungsgericht gestützt auf jene Einvernahme fest, dass sie nicht wusste, wie alt die Kinder im Zeitpunkt der Einreise waren. Weshalb diesbezüglich eine weitere Einvernahme hätte angeordnet werden sollen, ist nicht ersichtlich.
Entgegen der Ansicht des Beschwerdeführers trifft sodann zu, dass sie auf die Frage nach Eheproblemen ihre Krankheit, nicht aber den Zuzug der Kinder thematisierte. Auf die Frage "Lebten Sie zusammen? Gab es Probleme?" antwortete sie: "Zu Beginn verlief [alles] harmonisch. Gegen den Schluss wurde der Druck zuviel, ich mochte nicht mehr und fragte mich, warum wir überhaupt zusammen bleiben sollen. Ich bin krank seit ungefähr drei Jahren. Ich war viel im Spital und die Beziehung litt sehr darunter und führte zu Spannungen. Als ich nicht mehr arbeiten konnte, verschlechterte sich die Situation zusehends." Auch in dieser Hinsicht durfte die Vorinstanz ohne Verletzung von <ref-law> davon ausgehen, dass eine weitere Befragung am Beweisergebnis nichts ändern würde.
2.5.4 Unbehelflich sind schliesslich die Ausführungen des Beschwerdeführers zu den von der Vorinstanz festgestellten Ungereimtheiten im Aussageverhalten seiner Familienangehörigen. Zum einen handelt es sich bei diesen vorinstanzlichen Feststellungen lediglich um Hilfserwägungen, welche den angefochtenen Entscheid offensichtlich nicht entscheidend beeinflussten. Zum andern äussert sich der Beschwerdeführer zu den betreffenden Erwägungen lediglich selektiv. Das Bundesverwaltungsgericht sah die Glaubwürdigkeit der mazedonischen Ehefrau des Beschwerdeführers nicht nur deshalb in Frage gestellt, weil sie behauptete, ihre Kinder nicht zur Botschaft in Skopje begleitet zu haben. Es wies auch darauf hin, dass sie am 12. Dezember 2000, als sie ein Gesuch für ein Visum stellte, erklärte, sie sei verheiratet, ihr Ehemann lebe in Kroatien und ihre beiden Kinder besuchten in ihrer Heimatstadt die 7. bzw. die 8. Schulklasse. Darauf geht der Beschwerdeführer nicht ein.
Die Vorinstanz durfte demnach willkürfrei davon ausgehen, dass die Zeugenbefragung der Tante und des Grossvaters der beiden Kinder am Beweisergebnis nichts geändert hätten. Eine Verletzung des rechtlichen Gehörs liegt nicht vor.
2.6 Der Beschwerdeführer hat nicht plausibel dargelegt, dass der Nachzug der Kinder als ausserordentliches, nach der erleichterten Einbürgerung eingetretenes Ereignis zum raschen Scheitern der Ehe geführt hat. Die Vorinstanz bejahte die Voraussetzungen für die Nichtigerklärung der erleichterten Einbürgerung zu Recht. Das mit der Gehörsrüge verbundene Vorbringen, die Vorinstanz habe <ref-law> verletzt, erweist sich als unbegründet.
3. 3.1 Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann.
3.2 Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Prozessführung. Nach <ref-law> befreit das Bundesgericht eine Partei, die nicht über die erforderlichen Mittel verfügt, auf Antrag von der Bezahlung der Gerichtskosten, sofern ihr Rechtsbegehren nicht aussichtslos erscheint. Nach der bundesgerichtlichen Rechtsprechung sind Prozessbegehren als aussichtslos anzusehen, bei denen die Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können. Massgebend ist, ob eine Partei, die über die nötigen finanziellen Mittel verfügt, sich bei vernünftiger Überlegung zu einem Prozess entschliessen würde; eine Partei soll einen Prozess, den sie auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er sie nichts kostet (<ref-ruling> E. 2.3.1 S. 135 f.; <ref-ruling> E. 5 S. 616; je mit Hinweisen). Ob eine Beschwerde aussichtsreich ist, erschliesst sich aus den Begehren und ihrer Begründung durch den Beschwerdeführer (Urteil 6B_588/2007 vom 11. April 2008 E. 6.2, in: Pra 2008 Nr. 123 S. 766). Wie sich aus der vorangehenden Erwägung 2 ergibt, sind die Rügen der Verletzung von <ref-law> und <ref-law> offensichtlich unbegründet. Infolge Aussichtslosigkeit des Rechtsmittels entfällt deshalb der Anspruch auf unentgeltliche Rechtspflege nach <ref-law>. Der Beschwerdeführer trägt somit die Gerichtskosten (<ref-law>). Er hat zudem keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 1'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, 25. Mai 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold