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.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Nach Art. 100 Abs. 1 lit. c OG ist die Verwaltungsgerichtsbeschwerde auf dem Gebiet des Schweizer Bürgerrechts nur ausgeschlossen, wenn es sich um die Erteilung oder Verweigerung der Bewilligung für die ordentliche Einbürgerung handelt. Daraus folgt umgekehrt, dass die Verwaltungsgerichtsbeschwerde zulässig ist, wenn es um die erleichterte Einbürgerung geht und damit auch, wenn der Widerruf einer solchen zur Beurteilung steht (<ref-ruling>, nicht publizierte E. 1). Die Eingabe des Beschwerdeführers erfüllt die Formvorschriften von Art. 108 Abs. 2 OG und richtet sich gegen einen anfechtbaren Departementsentscheid (Art. 98 lit. b OG). Auf die fristgerecht (Art. 106 Abs. 1 OG) eingereichte Beschwerde ist daher einzutreten. Das Bundesgericht überprüft den Sachverhalt und das Bundesrecht frei (Art. 104 lit. a und b sowie Art. 105 Abs. 1 OG).
1.2 Unzulässig ist der Antrag des Beschwerdeführers, die Verfügung des IMES vom 19. August 2003 aufzuheben, denn Anfechtungsobjekt bildet einzig der Entscheid des EJPD (Art. 98 lit. b OG).
1.3 Insoweit der Beschwerdeführer auf die Beschwerdeschrift vom 17. September 2003 seines vormaligen Rechtsvertreters hinweist, kann darauf nicht eingetreten werden. Denn die Begründung muss in der Verwaltungsgerichtsbeschwerde selbst enthalten sein (Art. 108 Abs. 2 OG; <ref-ruling> E. 3.2 S. 406 mit Hinweis).
2. Gemäss Art. 27 Abs. 1 BüG kann ein Ausländer nach der Eheschliessung mit einer Schweizer Bürgerin ein Gesuch um erleichterte Einbürgerung stellen, wenn er insgesamt fünf Jahre in der Schweiz gewohnt hat, seit einem Jahr hier wohnt und seit drei Jahren in ehelicher Gemeinschaft mit der Schweizer Bürgerin lebt. Das Bundesgericht geht davon aus, dass eine eheliche Gemeinschaft im Sinne von Art. 27 BüG nicht nur das formelle Bestehen einer Ehe, sondern das Vorliegen einer tatsächlichen Lebensgemeinschaft voraussetzt. Eine solche Gemeinschaft kann nur bejaht werden, wenn der gemeinsame Wille zu einer stabilen ehelichen Gemeinschaft intakt ist (<ref-ruling> E. 2.3.1). Gemäss konstanter Praxis muss 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 solchen Willens sind angebracht, wenn kurze Zeit nach der erleichterten Einbürgerung die Trennung erfolgt oder die Scheidung eingeleitet wird. Der Gesetzgeber wollte dem ausländischen Ehegatten einer Schweizer Bürgerin oder eines Schweizer Bürgers die erleichterte Einbürgerung ermöglichen, um die Einheit des Bürgerrechts der Ehegatten im Hinblick auf ihre gemeinsame Zukunft zu fördern (<ref-ruling> E. 3a).
Nach Art. 41 Abs. 1 BüG kann die Einbürgerung vom EJPD mit Zustimmung der Behörde des Heimatkantons innert fünf Jahren nichtig erklärt werden, wenn sie durch falsche Angaben oder Verheimlichung erheblicher Tatsachen erschlichen worden ist. Das blosse Fehlen der Einbürgerungsvoraussetzungen genügt daher nicht. Die Nichtigerklärung der Einbürgerung setzt vielmehr voraus, dass diese erschlichen, das heisst mit einem unlauteren und täuschenden Verhalten erwirkt worden ist (<ref-ruling> E. 4a S. 101). Arglist im Sinne des strafrechtlichen Betrugstatbestands ist nicht erforderlich. Immerhin ist notwendig, dass der Betroffene bewusst falsche Angaben macht bzw. die Behörde bewusst in einem falschen Glauben lässt und so den Vorwurf auf sich zieht, es unterlassen zu haben, die Behörde über eine erhebliche Tatsache zu informieren (Urteil des Bundesgerichts 5A.5/ 1997 vom 21. Mai 1997, E. 2b).
3. 3.1 Das Bundesamt für Zuwanderung, Integration und Auswanderung (IMES) hat am 19. August 2003 die erleichterte Einbürgerung des Beschwerdeführers vom 2. September 1998 für nichtig erklärt. Es hat sich dabei insbesondere auf die Scheidungsakten und die Befragung der Ex-Ehefrau vom 11. Oktober 2002 abgestützt und im Weiteren bei der früheren Arbeitgeberin des Beschwerdeführers die Gründe für die Auflösung des Arbeitsverhältnisses abgeklärt.
Das EJPD hat diese tatbeständlichen Grundlagen in seinem Entscheid übernommen und auf Grund der Einwände des Beschwerdeführers in seiner Verwaltungsbeschwerde sich seinerseits nochmals sehr ausführlich damit auseinander gesetzt. Es ist auf Grund der gesamten Umstände davon ausgegangen, dass der Beschwerdeführer durch ein planmässiges Vorgehen das Schweizer Bürgerrecht erschlichen habe und es ihm von allem Anfang an nicht darum gegangen sei, mit Y._ eine eheliche Gemeinschaft im Sinne von Art. 27 Abs. 1 BüG einzugehen. Dafür sprächen - wie bereits erwähnt - der grosse Altersunterschied zwischen den Ehegatten, die Umstände der Eheschliessung, das Verschweigen der beiden vorehelichen Kinder sowie auch der wahren Beziehung zur türkischen Mutter dieser Kinder, die Umstände der Kündigung und der nachfolgenden Suche einer Arbeitsstelle möglichst weit weg vom gemeinsamen Wohnort, und sodann die Scheidung von der Schweizer Ehefrau am 4. Mai 1999 sowie die anfangs Juli 1999 in der Türkei eingegangene Ehe mit der Mutter seiner Kinder. Gestützt auf diese Ereigniskette müsse sich der Beschwerdeführer entgegenhalten lassen, dass er die Erklärung über die eheliche Gemeinschaft am 6. September 1997 wider besseres Wissen unterzeichnet habe. Durch das gezielte Irreführen der Schweizer Ehefrau und der Einbürgerungsbehörden habe der Beschwerdeführer den Tatbestand des Rechtsmissbrauchs erfüllt. Auch habe er das Institut der Ehe zweckwidrig zur Verwirklichung von Interessen verwendet, die dieses Rechtsinstitut nicht schützen wolle (vgl. <ref-ruling> E. 5a zu Art. 7 ANAG [SR 142.20]).
3.2 In der Bundesverwaltungsrechtspflege gilt der Grundsatz der freien Beweiswürdigung (Art. 19 VwVG i.V.m. Art. 40 BZP). Frei ist die Beweiswürdigung vor allem darin, dass sie nicht an bestimmte starre Beweisregeln gebunden ist, die dem Richter genau vorschreiben, wie ein gültiger Beweis zu Stande kommt und welchen Beweiswert die einzelnen Beweismittel im Verhältnis zueinander haben (Fritz Gygi, Bundesverwaltungsrechtspflege, 2. Aufl. Bern 1983, S. 278/279; zu den Beweismitteln: <ref-ruling> E. 2.3.2 ff.). Für eine belastende Verfügung - wie hier - trägt die Verwaltung die Beweislast. Bei der Nichtigerklärung einer erleichterten Einbürgerung ist von der Verwaltung zu untersuchen, ob die Ehe im massgeblichen Zeitpunkt der Gesuchseinreichung und der Einbürgerung tatsächlich gelebt wurde (<ref-ruling> E. 2.3.1 S. 172). Im Wesentlichen geht es dabei um innere Vorgänge, die der Verwaltung oft nicht bekannt und schwierig zu beweisen sind. Sie kann sich daher veranlasst sehen, von bekannten Tatsachen (Vermutungsbasis) auf unbekannte (Vermutungsfolge) zu schliessen. Tatsächliche Vermutungen können sich in allen Bereichen der Rechtsanwendung ergeben, namentlich auch im öffentlichen Recht. Es handelt sich dabei um Wahrscheinlichkeitsfolgerungen, die auf Grund der Lebenserfahrung gezogen werden (Ulrich Häfelin, Vermutungen im öffentlichen Recht, in: Festschrift für Kurt Eichenberger, Basel 1982, S. 626; vgl. auch Peter Sutter, Die Beweislastregeln unter besonderer Berücksichtigung des verwaltungsrechtlichen Streitverfahrens, Diss. Zürich 1988, S. 56 ff., 178 ff. und Fritz Gygi, a.a.O., S. 282 ff.; Max Kummer, Berner Kommentar, N. 362 f. zu Art. 8 ZGB).
Als Problem der Beweiswürdigung berührt die tatsächliche Vermutung weder die Beweislast noch die das Verwaltungsverfahren beherrschende Untersuchungsmaxime. Letztere gebietet zwar, dass die Verwaltung auch nach entlastenden, das heisst die Vermutung erschütternden Elementen sucht. Nun liegt es beim vorliegend zur Diskussion stehenden Thema in der Natur der Sache, dass solche der Verwaltung oft nicht bekannt sein dürften und nur der Betroffene darüber Bescheid weiss. Es ist daher Sache des Betroffenen, der nicht nur zur Mitwirkung verpflichtet ist (Art. 13 VwVG), sondern angesichts der gegen ihn sprechenden tatsächlichen Vermutung selber ein eminentes Interesse daran hat, die Vermutung durch den Gegenbeweis bzw. erhebliche Zweifel umzustürzen, indem er Gründe bzw. Sachumstände aufzeigt, die es als überzeugend (nachvollziehbar) erscheinen lassen, dass eine angeblich noch wenige Monate zuvor bestehende tatsächliche, ungetrennte eheliche Gemeinschaft in der Zwischenzeit dergestalt in die Brüche gegangen ist, dass es zur Scheidung kam.
3.3 Bis zur Einreise am 3. Juli 1989 in die Schweiz lebte der Beschwerdeführer mit einer türkischen Frau zusammen, mit der er zwei Kinder gezeugt hat. 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 einer um 26 Jahre älteren Schweizer Bürgerin an. Die Heirat erfolgte am 22. Januar 1993. Am 6. September 1997 unterschrieb der Beschwerdeführer eine Erklärung, wonach er und seine Schweizer Ehefrau in einer stabilen ehelichen Gemeinschaft lebten. Das Schweizer Bürgerrecht wurde dem Beschwerdeführer am 2. September 1998 verliehen und am 1. März 1999 unterzeichnete er mit seiner Schweizer Ehefrau die Vereinbarung zur Auflösung des Haushaltes und der Ehe, worauf am 4. Mai 1999 die Scheidung ausgesprochen wurde. Am 6. Juli 1999 verheiratete sich der Beschwerdeführer mit seiner früheren Lebensgefährtin.
Allein auf Grund dieser Eckdaten besteht die Vermutung, dass der Beschwerdeführer und seine Ehefrau im fraglichen Zeitpunkt nicht (mehr) in einer stabilen ehelichen Gemeinschaft lebten und infolgedessen die unmittelbar vor der Scheidung und Wiederverheiratung erlangte erleichterte Einbürgerung erschlichen wurde. Der Beschwerdeführer bringt in seiner Beschwerde in der Hauptsache vor, die Ehe sei auf Grund der wirtschaftlichen Probleme nach der Kündigung (Januar 1999) gescheitert. Er sei deswegen psychisch angeschlagen und, bedingt durch die Stellensuche, häufig abwesend gewesen. Es ist nicht von der Hand zu weisen, dass wirtschaftlich angespannte Verhältnisse Ehen gefährden können. Hier geht es aber darum, ob nachvollziehbar ist, dass eine bis zum Januar 1999 angeblich intakte Ehe infolge der Kündigung der Arbeitsstelle innert nicht einmal ganz zweier Monate derart zerrüttet wurde, dass die Ehegatten eine Scheidungsvereinbarung unterzeichneten. Das ist nach der allgemeinen Lebenserfahrung zu verneinen, weshalb der Beschwerdeführer die tatsächliche Vermutung nicht umzustossen vermag. Eine Auseinandersetzung mit den weiteren Vorbringen des Beschwerdeführers, insbesondere dass die Ehe mit der Schweizer Ehefrau trotz seiner Ferienaufenthalte in der Türkei bis zur Ehescheidung intensiv gelebt worden sei, erübrigt sich daher.
4. Die Verwaltungsgerichtsbeschwerde muss nach dem Ausgeführten abgewiesen werden, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang trägt der Beschwerdeführer die Gerichtskosten (Art. 156 Abs. 1 OG).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer und dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
Lausanne, 7. September 2004
Im Namen der II. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: