Sachverhalt:
A. Mit Urteil vom 30. Mai 2003 schied das Bezirksgericht Prizren, Kosovo, die Ehe zwischen A.X._ und B.X._.
Am 7. Oktober 2003 verfügte das Departement des Innern des Kantons Aargau, Sektion Bürgerrecht und Personenstand, die Anerkennung und Eintragung der ausländischen Scheidung in die Zivilstandsregister des Wohnortes von A.X._.
B. Am 8. März 2004 reichte B.X._ beim Obergericht des Kantons Aargau Beschwerde ein und beantragte, die Verfügung vom 7. Oktober 2003 betreffend Anerkennung und Eintragung sei aufzuheben. Das Obergericht hiess die Beschwerde mit Urteil vom 1. Juni 2004 teilweise gut und hob die angefochtene Verfügung auf.
C. A.X._ gelangt mit Verwaltungsgerichtsbeschwerde an das Bundesgericht. Er beantragt die Aufhebung des obergerichtlichen Urteils, soweit darin die Anerkennung und Eintragung des ausländischen Scheidungsurteils in die Zivilstandsregister verweigert worden ist. Weiter verlangt er, es sei festzustellen, dass die Ehe zwischen ihm und B.X._ rechtskräftig geschieden sei. Zudem stellt er ein Gesuch um unentgeltliche Rechtspflege einschliesslich Verbeiständung.
B.X._ schliesst in ihrer Vernehmlassung auf Abweisung der Beschwerde. Ferner stellt sie ebenfalls ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung. Das Eidgenössische Justiz- und Polizeidepartement hat auf eine Stellungnahme verzichtet.

Das Bundesgericht zieht in Erwägung:
1. Auf den 1. Juli 2004 ist die neue Zivilstandsverordnung vom 28. April 2004 (ZStV; SR 211.112.2) in Kraft getreten. Auf den vorliegenden Fall, welchen das Obergericht am 1. Juni 2004 entschieden hat, findet noch die alte Zivilstandsverordnung vom 1. Juni 1953 Anwendung. Bezüglich des zulässigen Rechtsmittels hat indes die Revision keine Änderung gebracht. Sowohl nach Art. 20 aZStV wie auch nach Art. 90 [n]ZStV kann gegen die Verweigerung der Eintragung eines ausländischen Scheidungsurteils in die Zivilstandsregister Verwaltungsgerichtsbeschwerde an das Bundesgericht geführt werden. Das angefochtene Urteil betrifft den Zivilstand des Beschwerdeführers, er hat daher ein eigenes und unmittelbares Interesse an der Beschwerdeführung (Art. 103 lit. a OG). Die fristgerecht (Art. 106 Abs. 1 OG) erhobene Verwaltungsgerichtsbeschwerde erweist sich folglich als zulässig.
2. Neben dem Antrag auf Aufhebung des angefochtenen Urteils, soweit darin die Anerkennung und Eintragung des ausländischen Scheidungsurteils in die Zivilstandsregister verweigert worden ist, beantragt der Beschwerdeführer auch die Feststellung, dass er von der Beschwerdegegnerin rechtskräftig geschieden sei. Streitgegenstand im vorliegenden Verfahren ist indes nur die Frage der Anerkennungs- und Eintragungsfähigkeit des ausländischen Scheidungsurteils in die Zivilstandsregister; auf das selbstständige Feststellungsbegehren kann nicht eingetreten werden.
3. Der Beschwerdeführer rügt zunächst eine fehlerhafte Feststellung des Sachverhaltes im Sinne von Art. 104 lit. b OG. Dabei ist zu beachten, dass es sich beim Obergericht, welches das angefochtene Urteil gefällt hat, um eine richterliche Behörde handelt. Gemäss Art. 105 Abs. 2 OG ist in einem solchen Fall die Feststellung des Sachverhaltes für das Bundesgericht verbindlich, wenn die Vorinstanz diesen nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt hat. Der Beschwerdeführer macht mit dieser Rüge in erster Linie geltend, das Obergericht habe die von der Beschwerdegegnerin unterzeichnete Anwaltsvollmacht zu Unrecht nicht als Erklärung ihres Scheidungswillens an das zuständige Gericht gewertet. Dabei handelt es sich indes nicht um eine Sachverhaltsfeststellung, sondern um eine Rechtsfrage, die das Bundesgericht im vorliegenden Beschwerdeverfahren frei prüfen kann (<ref-ruling> E. 6a S. 54 f.).
3.1 Gemäss einer in albanischer Sprache verfassten Vollmacht vom 6. Mai 2003 hat die Beschwerdegegnerin einen Rechtsanwalt im Kosovo beauftragt, sie im Scheidungsverfahren zwischen ihr und dem Beschwerdeführer zu vertreten. Konkret wird der Anwalt "zur Vertretung vor dem Bezirksgericht in Prizren betreffend die einvernehmliche Auflösung der ehelichen Gemeinschaft" bevollmächtigt. Die Anwaltsvollmacht ist mit einer von einem schweizerischen Notar beglaubigten Unterschrift der Beschwerdegegnerin versehen.
Aus der Wendung "einvernehmliche Auflösung" der ehelichen Gemeinschaft lässt sich das Einverständnis der Beschwerdegegnerin zur Scheidung ableiten. Bereits das Obergericht hat festgestellt, die Beschwerdegegnerin habe mit der Vollmacht den Anwalt mit der einvernehmlichen Auflösung der ehelichen Gemeinschaft beauftragt. Es ist folglich davon auszugehen, dass die Beschwerdegegnerin in der Anwaltsvollmacht ihre Zustimmung zur Ehescheidung erteilt hat. Dem entspricht im Übrigen das Scheidungsurteil des Bezirksgerichts Prizren vom 30. Mai 2003, welches beide Parteien als "Antragsteller" bezeichnet und von einer "gemeinsamen Ehescheidungsvereinbarung" spricht.
3.2 Damit ist weiter darüber zu befinden, ob die in der Vollmacht erklärte Zustimmung zur Ehescheidung als Erklärung an das Gericht angesehen werden kann. Dies hat das Obergericht verneint und aus diesem Grund die Anerkennung des Scheidungsurteils verweigert. Der Beschwerdeführer bringt dagegen vor, die Anwaltsvollmacht sei dafür vorgesehen, dem zuständigen Gericht eingereicht zu werden und daher geeignet, den Scheidungswillen der Beschwerdegegnerin gegenüber dem Scheidungsgericht zu manifestieren.
Es ist tatsächlich nicht ersichtlich, welchem anderen Zweck als der Geltendmachung vor dem zuständigen Gericht der in der Vollmacht geäusserte Scheidungswille dienen könnte. So wird der Anwalt ausdrücklich mit der Vertretung vor Gericht beauftragt. Dass der Inhalt der Erklärung (auch) für das Gericht bestimmt ist, wird zudem dadurch bestätigt, als darin ausdrücklich festgehalten wird, dass es dem Bevollmächtigten "obliegt mitzuteilen", dass aus der Ehe keine Kinder hervorgegangen seien und beide Ehegatten in einem Arbeitsverhältnis stehen würden. Die in der Vollmacht enthaltene Erklärung des Scheidungswillens ist folglich als Erklärung an das Gericht zu verstehen.
4. Strittig ist weiter, ob die Anerkennung des Scheidungsurteils zu verweigern ist, weil die Beschwerdegegnerin ihren Scheidungswillen nicht persönlich vor dem Richter geäussert hat. Es stellt sich somit die Frage, ob die in Art. 111 Abs. 1 ZGB vorgesehene persönliche Anhörung der Ehegatten durch den Richter bei einer einvernehmlichen Scheidung zum schweizerischen Ordre public gehört.
4.1 Gemäss Art. 27 Abs. 1 IPRG kann eine ausländische Entscheidung in der Schweiz nicht anerkannt werden, wenn die Anerkennung mit der schweizerischen öffentlichen Ordnung offensichtlich unvereinbar wäre. Eine Anerkennung verstösst dann gegen den materiellen Ordre public, wenn das einheimische Rechtsgefühl durch die Anerkennung und Vollstreckung eines ausländischen Entscheids in unerträglicher Weise verletzt würde, weil dadurch grundlegende Vorschriften der schweizerischen Rechtsordnung missachtet werden. Die Anwendung des Ordre public-Vorbehaltes ist im Bereich der Anerkennung ausländischer Entscheide nach dem Wortlaut des Gesetzes restriktiver als im Bereich der Anwendung des fremden Rechts gemäss Art. 17 IPRG (<ref-ruling> E. 4a S. 629; <ref-ruling> E. 4a S. 348; <ref-ruling> E. 2b S. 330).
4.2 Die Beschwerdegegnerin leitet aus dem nicht publizierten Urteil des Bundesgerichts 5C.297/2001 vom 4. März 2002 (publ. in: Pra 2002 Nr. 87 S. 499) ab, die persönliche Teilnahme der Ehegatten am Scheidungsverfahren bzw. deren persönliche Anhörung gehöre zum schweizerischen Ordre public. In diesem Urteil hat das Bundesgericht vorab ausgeführt, eine einvernehmliche Scheidung verstosse gegen den Ordre public, wenn eine Partei vor dem Gericht nicht selber erkläre, sie willige in die Scheidung ein. Nach einem Hinweis auf das schweizerische Recht, das die persönliche Anhörung der Parteien im Scheidungsverfahren (Art. 111 Abs. 1 ZGB) sowie die schriftliche Bestätigung des Scheidungswillens nach einer Bedenkzeit (Art. 111 Abs. 2 ZGB) vorsieht, hat das Bundesgericht weiter festgehalten, es gehöre zu den Grundvoraussetzungen des schweizerischen Scheidungsrechts und entspreche daher gleichsam dem schweizerischen Ordre public, dass sich der Richter vom Scheidungswillen der Parteien hinreichend sicher überzeuge. Daher müsse auch in einem im Ausland durchgeführten Scheidungsverfahren der entsprechende Wille nachgewiesen sein, bevor der Richter die Scheidung einvernehmlich ausspreche. Das Bundesgericht hat in diesem Fall das ausländische Urteil für Ordre public-widrig gehalten, da überhaupt keine Erklärung der Ehefrau vorlag, mit der sie in die Scheidung einwilligte, und diese ohne ihr Wissen erfolgte.
Die Anerkennung einer einvernehmlichen Scheidung setzt nicht voraus, dass das ausländische Gericht entsprechend den Regeln von Art. 111 ZGB vorgegangen ist. Dagegen gehört das Erfordernis, dass eine Partei selber erklärt, sie willige in die Scheidung ein, und sich das Gericht vom Scheidungswillen der Parteien hinreichend überzeugt, zu den grundlegenden Prinzipien der schweizerischen Rechtsordnung. Die Gewissheit über den Scheidungswillen wird durch persönliche Anhörung der Parteien und schriftlicher Bestätigung des Scheidungswillens nach einer Bedenkzeit - wie in Art. 111 ZGB vorgesehen - optimal gewährleistet. Dies bedeutet indes nicht, dass der Scheidungswille nicht auch auf andere Weise nachgewiesen werden kann. Das Scheidungsgericht kann sich auch auf Grund einer schriftlichen Erklärung der Parteien hinreichend sicher von deren Einverständnis mit der Scheidung überzeugen. Dem entspricht BGE <ref-ruling>, in welchem das Bundesgericht festgehalten hat, ein Verstoss gegen Art. 27 Abs. 1 IPRG liege vor, wenn nur Repräsentanten der Familie zusammengetroffen seien und die Ehe bloss ihrerseits einverständlich aufgelöst haben, ohne dass beide Ehegatten anwesend oder damit zumindest einverstanden gewesen seien (E. 4b S. 439). Es ist folglich nicht ausgeschlossen, dass eine Scheidung auch anerkannt werden kann, wenn die Ehegatten nicht persönlich beim Verfahren anwesend gewesen sind. Im Übrigen wird in der Literatur zu Art. 111 ZGB teilweise die Ansicht vertreten, dass unter gewissen Umständen auf eine persönliche Anhörung verzichtet werden kann (Roland Fankhauser, in: Ingeborg Schwenzer [Hrsg.], Praxiskommentar Scheidungsrecht, N. 14 zu Art. 111 ZGB; Gloor, Basler Kommentar, N. 8 zu Art. 111 ZGB; Ruth Reusser, Die Scheidungsgründe und die Ehetrennung, in: Heinz Hausheer [Hrsg.], Vom alten zum neuen Scheidungsrecht, N. 1.35).
4.3 Im vorliegenden Fall ergibt sich die Zustimmung zur Scheidung aus der erwähnten Anwaltsvollmacht. Das Abstellen auf eine blosse Anwaltsvollmacht kann zwar heikel sein, insbesondere wenn nicht bekannt ist, unter welchem Umständen sie unterzeichnet worden ist. Hier ist nun aber die vor einem schweizerischen Notar unterzeichnete Vollmacht so konkret abgefasst (vgl. E. 3.1 vorangehend), dass am Einverständnis der Beschwerdegegnerin zur einvernehmlichen Scheidung keine Zweifel bestehen. Die Bedenken, welche die Beschwerdegegnerin in diesem Zusammenhang vorbringt (Widerruf der Vollmacht, ohne dass das Gericht davon Kenntnis erhält), sind rein theoretischer Natur, da sie nicht behauptet, sie habe die Vollmacht tatsächlich widerrufen. Im Verfahren vor Obergericht hat sie noch behauptet, keinen Anwalt mit der Scheidung beauftragt zu haben. Dies macht sie in der Verwaltungsgerichtsbeschwerde vor Bundesgericht nicht mehr geltend und bestreitet insbesondere nicht mehr, die Vollmacht unterschrieben zu haben. Hingegen erklärt sie in einem nach Ablauf der Vernehmlassungsfrist eingereichten Schreiben betreffend ihre Bedürftigkeit, sie sei - der deutschen Sprache nicht mächtig - getäuscht worden und habe geglaubt, eine Lebensversicherung zu unterschreiben. Abgesehen davon, dass diese Erklärung verspätet ist, erweist sie sich als offensichtlich aktenwidrig, ist doch die Anwaltsvollmacht in albanischer Sprache verfasst. Zudem ergibt sich aus den Akten, dass die Beschwerdegegnerin am 20. Dezember 2003 anlässlich einer Einvernahme gegenüber der Kantonspolizei Aargau zum Stichwort Heirat vorbehaltlos erklärt hat, sie sei seit dem 30. Mai 2003 (dies entspricht dem Datum des Scheidungsurteils des Bezirksgerichts Prizren) geschieden und zum Stichwort Eheleben, "schlecht, aus diesem Grund haben wir geschieden". Die Behauptung der Beschwerdegegnerin, entgegen dem Anschein der von ihr unterzeichneten Vollmacht ohne ihre Einwilligung geschieden worden zu sein, erweist sich folglich als aktenwidrig.
Zusammenfassend ist festzuhalten, dass auf Grund der Akten das Einverständnis der Beschwerdegegnerin mit der Scheidung klar dokumentiert ist und das Scheidungsgericht sich von ihrem Scheidungswillen durch die Vollmacht hinreichend sicher überzeugen konnte. Die Einwendungen der Beschwerdegegnerin erweisen sich als aktenwidrig und unglaubwürdig.
4.4 Dementsprechend verstösst die Anerkennung des Urteils des Bezirksgerichts Prizren vom 30. Mai 2003 nicht gegen den schweizerischen Ordre public und die Scheidung der Parteien kann in die Zivilstandsregister eingetragen werden. Die Verwaltungsgerichtsbeschwerde ist insoweit gutzuheissen. Mit der Aufhebung des obergerichtlichen Urteils tritt die Verfügung des Departement des Innern des Kantons Aargau vom 7. Oktober 2003 wieder in Kraft.
5. Bei diesem Verfahrensausgang wird die Beschwerdegegnerin grundsätzlich kosten- und entschädigungspflichtig (Art. 156 Abs. 1 und Art. 159 Abs. 2 OG). Beide Parteien haben ein Gesuch um unentgeltliche Rechtspflege gestellt, dessen Voraussetzungen (Art. 152 OG) erfüllt sind, soweit das Gesuch des obsiegenden Beschwerdeführers nicht ohnehin gegenstandslos geworden ist. Da beide Parteien offensichtlich nicht über ausreichende Mittel für die Bestreitung der Prozesskosten verfügen, ist der Rechtsbeistand des Beschwerdeführers ohne Vorbehalt der Einbringlichkeit direkt aus der Bundesgerichtskasse zu entschädigen (Art. 152 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird gutgeheissen, soweit darauf einzutreten ist, und Ziff. 1 des Urteils des Obergerichts des Kantons Aargau, 3. Zivilkammer, vom 1. Juni 2004 wird aufgehoben.
2. 2.1 Das Gesuch um unentgeltliche Rechtspflege des Beschwerdeführers wird gutgeheissen, soweit es nicht gegenstandslos geworden ist, und Fürsprecher Christian Märki wird ihm als unentgeltlicher Rechtsbeistand beigegeben.
2.2 Das Gesuch um unentgeltliche Rechtspflege der Beschwerdegegnerin wird gutgeheissen, und Rechtsanwältin Barbara Lind wird ihr als unentgeltlicher Rechtsbeistand beigegeben.
3. Die Gerichtsgebühr von Fr. 2'000.-- wird der Beschwerdegegnerin auferlegt, einstweilen jedoch auf die Bundesgerichtskasse genommen.
4. 4.1 Fürsprecher Christian Märki wird aus der Bundesgerichtskasse ein Honorar von Fr. 1'500.-- ausgerichtet.
4.2 Rechtsanwältin Barbara Lind wird aus der Bundesgerichtskasse ein Honorar von Fr. 1'000.-- ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, 3. Zivilkammer, sowie dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
Lausanne, 26. Januar 2005
Im Namen der II. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: