Sachverhalt: A. A.a X._ reiste am 3. Juli 1989 in die Schweiz ein und ersuchte hier um Asyl. Nach rechtskräftigem Abschluss des Asylverfahrens wurde er aufgefordert, die Schweiz bis zum 30. November 1992 zu verlassen. Stattdessen meldete er im November 1992 das Eheversprechen mit der um 26 Jahre älteren Schweizer Bürgerin Y._ an. Am 22. Januar 1993 fand dann die Heirat statt. Am 2. September 1998 erhielt X._ durch erleichterte Einbürgerung nach Art. 27 BüG das Schweizer Bürgerrecht. In diesem Zusammenhang unterzeichnete er am 6. September 1997 eine Erklärung, wonach er und seine Schweizer Ehefrau "in einer tatsächlichen, ungetrennten, stabilen ehelichen Gemeinschaft an derselben Adresse zusammenleben und dass weder Trennungs- noch Scheidungsabsichten bestehen". Er wurde auch darüber belehrt, 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. X._ wurde am 4. Mai 1999 von seiner Schweizer Ehefrau geschieden und heiratete am 6. Juli 1999 die türkische Staatsangehörige Z._. A.b Das Bundesamt für Zuwanderung, Integration und Auswanderung (IMES) teilte am 27. August 2001 X._ die Eröffnung eines Verfahrens um Nichtigerklärung der erleichterten Einbürgerung mit. Sein Parteivertreter nahm dazu mit Eingabe vom 10. September 2001 Stellung. Nach Einsichtnahme in die Scheidungsakten des Gerichtskreises III Aarberg-Büren-Erlach forderte das IMES X._ auf, nähere Angaben zu seinem letzten Arbeitstag und die nachfolgende Stellensuche zu machen. Dabei wurden auch Auskünfte von der früheren Arbeitgeberin mit Bezug auf die Kündigung des Arbeitsverhältnisses eingeholt. A.c Am 10. September 2002 ersuchte das IMES den Zivilstands- und Bürgerrechtsdienst des Kantons Bern, die Schweizer Ex-Ehefrau zu den Umständen der Eheschliessung und der Scheidung sowie zum Verlauf der Ehe zu befragen. Die Befragung erfolgte am 11. Oktober 2002 durch die Kantonspolizei. In der abschliessenden Stellungnahme vom 7. März 2003 führte der Parteivertreter von X._ aus, sowohl aus den Scheidungsakten wie auch aus der Befragung der Ex-Ehefrau ergebe sich klar, dass die Ehe bis anfangs 1999 stabil gewesen bzw. an der Arbeitslosigkeit seines Mandanten gescheitert sei. B. B.a Mit Verfügung vom 19. August 2003 erklärte das IMES die erleichterte Einbürgerung von X._ vom 2. September 1998 für nichtig. Am 30. April 2004 wies das Eidgenössische Justiz- und Polizeidepartement (EJPD) die von X._ eingereichte Beschwerde ab. B.b Mit Eingabe vom 2. Juni 2004 führt X._ Verwaltungsgerichtsbeschwerde und beantragt, der Entscheid des EJPD vom 30. April 2004 sowie die Verfügung des IMES vom 19. August 2003 seien vollumfänglich aufzuheben; unter Kosten- und Entschädigungsfolgen zulasten der Schweizerischen Eidgenossenschaft. Es wurde keine Vernehmlassung eingeholt.