Sachverhalt:
A. X._ wurde 1971 geboren. Er stammt aus dem Kosovo. Im Januar 1995 gelangte er als Asylsuchender in die Schweiz. Am 6. Dezember 1995, während des hängigen Asylverfahrens, heiratete er die Schweizer Bürgerin A._. Er erhielt eine Aufenthaltsbewilligung und zog sein Asylgesuch zurück.
Am 16. April 1999 stellte X._ ein Gesuch um erleichterte Einbürgerung. Im Einbürgerungsverfahren unterzeichneten er und seine Ehefrau am 16. März 2001 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 6. April 2001 wurde X._ das Schweizer Bürgerrecht verliehen.
Die Ehe von X._ und A._ wurde am 12. Dezember 2001 geschieden. Am 8. November 2002 heiratete X._ eine Kosovarin.
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 9. März 2006 erklärte das BFM die erleichterte Einbürgerung für nichtig.
X._ focht diese Verfügung an. Mit Urteil vom 4. März 2009 wies das Bundesverwaltungsgericht die Beschwerde ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 17. April 2009 beantragt X._ im Wesentlichen, das Urteil des Bundesverwaltungsgerichts und die Verfügung des BFM seien aufzuheben.
Das Bundesverwaltungsgericht verzichtet auf eine Vernehmlassung. Das BFM beantragt die Abweisung der Beschwerde.

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.
1.2 Unzulässig ist der Antrag des Beschwerdeführers, die Verfügung des BFM vom 9. März 2006 sei aufzuheben. Diese ist durch das Urteil des Bundesverwaltungsgerichts vom 4. März 2009 ersetzt worden (Devolutiveffekt) und gilt als inhaltlich mitangefochten (<ref-ruling> E. 1.4 mit Hinweis).
1.3 Anfechtungsobjekt ist im bundesgerichtlichen Verfahren mithin ausschliesslich das Urteil des Bundesverwaltungsgerichts vom 4. März 2009. Insofern, als der Beschwerdeführer die Verfügung des BFM kritisiert, ohne damit eine nach <ref-law> zulässige Rüge gegenüber dem Urteil des Bundesverwaltungsgerichts zu verbinden, ist auf die Beschwerde nicht einzutreten.
1.4 Der Beschwerdeführer bringt vor, das BFM habe gegen die Dokumentationspflicht und den Anspruch auf rechtliches Gehör verstossen. Die Feststellung des Sachverhalts durch das BFM sei deshalb rechtswidrig. Das Bundesverwaltungsgericht habe in unzulässiger Weise auf den so festgestellten Sachverhalt abgestellt.
Im bundesgerichtlichen Verfahren dürfen neue Tatsachen und Beweismittel nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt, was in der Beschwerde näher darzulegen ist (<ref-law>; <ref-ruling> E. 2.2.1 S. 226 mit Hinweis). Zu den Tatsachen, zu deren Vorbringen erst der angefochtene Entscheid Anlass gibt, zählen insbesondere alle Umstände, die für die Anfechtung des Entscheids von Bedeutung sind (Eröffnung, Zustellung, Fristwahrung etc.), ferner Tatsachen zur Begründung gewisser formellrechtlicher Mängel (Verletzung des rechtlichen Gehörs, unrichtige Besetzung der Richterbank), mit denen nicht zu rechnen war, und schliesslich tatsächliche Vorbringen, die erst aufgrund einer neuen überraschenden rechtlichen Argumentation der Vorinstanz Rechtserheblichkeit erlangt haben. Dazu gehören aber nicht Tatsachenbehauptungen, die der Beschwerdeführer vorzutragen unterlassen hat, und die deshalb von der Vorinstanz auch nicht berücksichtigt werden konnten. Es ist nicht zulässig, mit neuen tatsächlichen Vorbringen, die schon vor der Vorinstanz hätten geltend gemacht werden können, nachzuweisen, dass die vorinstanzliche Sachverhaltsfeststellung offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sine von <ref-law> beruht (Urteil 4A_36/2008 vom 18. Februar 2008 E. 4.1 mit Hinweisen). Indem der Beschwerdeführer erstmals im bundesgerichtlichen Verfahren rügt, das BFM habe gegen die Dokumentationspflicht und den Anspruch auf rechtliches Gehör verstossen und das Bundesverwaltungsgericht habe unzulässigerweise auf den so festgestellten Sachverhalt abgestellt, tut er genau dies. Auf das Vorbringen ist demnach nicht einzutreten.
1.5 Der Beschwerdeführer rügt, dass die Vorinstanz das Schreiben seiner Ex-Ehefrau vom 21. März 2006 unberücksichtigt gelassen habe.
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Die Behebung des Mangels muss für den Ausgang des Verfahrens entscheidend sein (<ref-law>). Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss substanziiert darlegen, inwiefern die Voraussetzungen einer Ausnahme gemäss Art. 97 Abs. 1 bzw. <ref-law> gegeben sind. Er kann sich dabei nicht damit begnügen, den bestrittenen Feststellungen eigene tatsächliche Behauptungen gegenüberzustellen oder darzulegen, wie die Beweise seiner Ansicht nach zu würdigen gewesen wären. Vielmehr hat er klar und substanziiert aufzuzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (<ref-ruling> E. 2.4 S. 466 f. mit Hinweis).
Es trifft zu, dass das erwähnte Schreiben im angefochtenen Entscheid nicht erwähnt wird. Nach dem Gesagten ist jedoch die Sachverhaltsfeststellung durch die Vorinstanz für das Bundesgericht grundsätzlich verbindlich. Der Beschwerdeführer behauptet nicht, es lägen die Voraussetzungen einer Ausnahme gemäss Art. 97 Abs. 1 bzw. <ref-law> vor. Dies im Übrigen zu Recht, enthielten doch weder die Beschwerde vom 4. April 2006 an das Bundesverwaltungsgericht noch die anschliessende Replik vom 24. Juli 2006 entsprechende Ausführungen. Auf die Rüge ist deshalb nicht einzutreten.
1.6 Der Beschwerdeführer macht schliesslich eine Verletzung des Verhältnismässigkeitsprinzips (<ref-law>) geltend, weil allein wegen der zeitlichen Abfolge von Eheschliessung und Scheidung die Einbürgerung nach beinahe fünf Jahren für nichtig erklärt worden sei.
Nach <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt. Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (<ref-law>). Das setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die Begründungsanforderungen von <ref-law> erfüllt (<ref-ruling> E. 2.1 S. 245 f. mit Hinweisen).
Das Bundesverwaltungsgericht hat in seinem Urteil dargelegt, weshalb es nicht unverhältnismässig sei, wenn die Einbürgerung kurz vor Ablauf der Fünfjahresfrist von <ref-law> nichtig erklärt werde. Da sich der Beschwerdeführer mit diesen Ausführungen nicht auseinandersetzt, ist auf seine Rüge mangels hinreichender Begründung nicht einzutreten.
2. 2.1 Zusammenfassend ergibt sich, dass auf die Beschwerde nicht einzutreten ist.
2.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 (Abs. 1). Wenn es darüber hinaus zur Wahrung ihrer Rechte notwendig ist, bestellt das Bundesgericht der Partei einen Anwalt oder eine Anwältin (Abs. 2 Satz 1; Urteil 6B_482/2007 vom 12. August 2008 E. 21.2 mit Hinweisen). 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. 5 S. 616; <ref-ruling> E. 2.3.1 S. 135 f.; 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 den vorangehenden Erwägungen ergibt, ist vorliegend das Rechtsmittel aussichtslos. Damit entfällt 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. Auf die Beschwerde wird nicht eingetreten.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4. Es wird keine Parteientschädigung zugesprochen.
5. Dieses Urteil wird dem Beschwerdeführer, dem Bundesamt für Migration und dem Bundesverwaltungsgericht, Abteilung III, schriftlich mitgeteilt.
Lausanne, 18. Juni 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold