Sachverhalt: A. Die Parteien heirateten 1998 in A._. Der Ehe entstammen der gemeinsame Sohn D._, geb. 1998, und die gemeinsame Tochter E._, geb. 2000. Seit 2000 leben die Parteien getrennt. B. Mit Urteil vom 15. Juli 2003 schied das Amtsgericht B._ die Ehe. Dabei stellte es die Kinder unter die elterliche Sorge der Mutter und gewährte dem Vater an jedem ersten und dritten Wochenende eines Monats ein Besuchsrecht von Samstag, 08.00 Uhr, bis Sonntag, 18.00 Uhr, sowie ein Ferienrecht von zwei Wochen pro Jahr. Sodann hob es die Beistandschaft auf und regelte die weiteren Nebenfolgen der Scheidung. Mit Bezug auf das Besuchs- und Ferienrecht und die Aufhebung der Beistandschaft erhob die Mutter Appellation. Mit Urteil vom 30. März 2004 erlaubte das Obergericht des Kantons Luzern, II. Kammer, dem Vater, die Kinder bis Ende Juli 2005 an jedem zweiten und vierten Sonntag des Monats von 13.30 bis 18.00 Uhr im Rahmen eines begleiteten Besuchsrechts der Pro Juventute in C._ zu besuchen; ab August 2005 gewährte es ihm ein unbegleitetes Besuchsrecht an jedem zweiten und vierten Sonntag des Monates von 09.00 bis 18.00 Uhr, für die ersten drei Besuche unter Aufsicht der Beiständin. Sodann ordnete es an, dass die bestehende Beistandschaft nach Art. 308 Abs. 1 und 2 ZGB aufrecht erhalten bleibe. C. Gegen dieses Urteil hat der Vater am 19. Mai 2004 Berufung eingereicht mit dem Begehren um Aufhebung der entsprechenden Anordnungen und Bestätigung des erstinstanzlichen Entscheids. Eventualiter verlangt er bis Ende Juli 2005 ein unbeaufsichtigtes Besuchsrecht am ersten Wochenende eines jeden Monats von Samstag, 08.00 Uhr, bis Sonntag, 18.00 Uhr, sowie am 26. Dezember und Ostermontag von 10.00 bis 18.00 Uhr und ein Ferienrecht von zwei Wochen sowie eine dem erstinstanzlichen Urteil entsprechende Regelung für die Zeit ab August 2005. Subeventualiter stellt er einen Antrag auf Rückweisung der Sache an die Vorinstanz. Zudem verlangt er die unentgeltliche Rechtspflege. Die Mutter schliesst in ihrer Berufungsantwort vom 16. Juli 2004 auf Abweisung der Berufung und verlangt ebenfalls die unentgeltliche Rechtspflege.