Sachverhalt: A. X._ (nachfolgend: Beschwerdeführer) und Y._ (nachfolgend: Beschwerdegegnerin) sind die Eltern von A._, geboren 1994, und B._, geboren 1996. Seit acht Jahren werden die Kinder vom Beschwerdeführer alleine betreut. Nachdem der Beschwerdeführer mit den beiden Kindern Ende 2003 in die Wohnung seiner Mutter nach C._ gezogen war, beantragte er die alleinige elterliche Sorge. Ein am 21. Oktober 2004 erstelltes Gutachten der kantonalen Erziehungsberatung C._ kam zum Schluss, dass die Erziehungsfähigkeit der Beschwerdegegnerin und in gewissen Bereichen auch die des Beschwerdeführers eingeschränkt sei. Auch die Kooperationsfähigkeit bezüglich der Erziehung sei ungenügend. Die Voraussetzungen zur Übernahme der elterlichen Sorge durch den Beschwerdeführer sei demnach nicht sicher gegeben. Am 30. Juni/18. August 2007 schlossen die Parteien eine Vereinbarung ab, welche unter anderem Folgendes vorsieht: "Herr X._ wird - solange die räumliche Trennung noch andauert - unter der Woche mit den beiden Kindern in D._ Mittagessen (...) und jedes Wochenende mindestens einen Tag (Samstag oder Sonntag) ebenfalls in D._ verbringen. Herr X._ wird jeden zweiten Samstag seine Abwesenheit ausbauen, damit der Wunsch von Frau Y._, mit den beiden Kindern auch allein Zeit zu verbringen, möglichst bald realisiert werden kann." Die Parteien beantragten in der Vereinbarung die gemeinsame elterliche Sorge, und der Beschwerdeführer zog seinen Antrag auf die alleinige elterliche Sorge zurück. Am 19. Oktober 2007 wurde die Vereinbarung von der Vormundschaftsbehörde E._ genehmigt. Am 1. April 2008 zog die Beschwerdegegnerin in eine neue Wohnung. B. Am 20. Mai 2008 stellte der Beschwerdeführer bei der Einwohnergemeinde E._, Sozial- und Vormundschaftsbehörde, ein Gesuch gemäss Art. 313 Abs. 1 ZGB und beantragte, dass die in der zwischen ihm und der Beschwerdegegnerin geschlossenen Vereinbarung vorgesehene Besuchsregelung betreffend die beiden Kinder A._ und B._ den veränderten Verhältnissen anzupassen sei. Die Beschwerdegegnerin stellte am 9. Juli 2008 das Begehren um Ergreifung der notwendigen Kindesschutzmassnahmen und um Einsetzung eines Kindsvertreters. C. Am 11. September 2008 verfügte die Vormundschaftsbehörde E._ unter anderem Folgendes: "1. Auf eine vertrauensärztliche Abklärung von Frau Y._ wird verzichtet (...). 2. Auf einen Wechsel der Familienbegleiterin von Frau F._ zu Frau G._ wird verzichtet. (...) 3. Die Besuchsregelung wird neu wie folgt festgelegt: Im ersten Besuchsmonat sind die Kinder A._ und B._, jeweils samstags oder sonntags (ist von den Freizeit- und Sportaktivitäten der Kinder abhängig), im vierzehntäglichen Abstand, von 13.30 bis 18.00 Uhr und im zweiten Besuchsmonat jeweils samstags oder sonntags, ebenfalls im vierzehntäglichen Abstand, von 10.00 bis 20.00 Uhr bei der Mutter alleine zu Besuch. Die Besuche finden in der neuen Wohnung von Frau Y._ statt. Die Familienbegleiterin, Frau F._, ist am ersten Besuchssamstag oder -sonntag während drei bis vier Stunden und ab dem zweiten Besuchssamstag oder -sonntag während rund zwei Stunden bei Frau Y._ und den Kindern anwesend. Frau F._ kann bei Bedarf die Besuche der Kinder bei Frau Y._ begleiten. Diese werden sich aufgrund der Rückmeldungen von Frau F._ abzeichnen. (...) 6. Die Umsetzung und Einhaltung der Besuchsregelung ist durch den Beistand H._, Regionaler Sozialdienst K._, zu überwachen." D. Gegen diese Verfügung führte der Beschwerdeführer am 19. September 2008 beim Regierungsstatthalter von L._ Beschwerde, welche mit Entscheid vom 9. Februar 2009 abgewiesen wurde. E. Dagegen erhob der Beschwerdeführer am 23. Februar 2009 Beschwerde beim Appellationshof des Obergerichts des Kantons Bern, welches die Verfügung der Vormundschaftsbehörde E._ mit Entscheid vom 17. April 2009 in den oben (Bst. C) erwähnten Punkten bestätigte. F. Mit Beschwerde vom 20. Mai 2009 beantragt der Beschwerdeführer dem Bundesgericht, es sei der Entscheid des Obergerichts aufzuheben und die in der Vereinbarung vom 30. Juni/18. August 2007 vorgesehene Besuchsregelung zum Wohle der Kinder den veränderten Verhältnissen anzupassen, eventualiter sei die Sache an die Vorinstanz zurückzuweisen. In der Sache wurden keine Vernehmlassungen eingeholt. Die Beschwerdegegnerin beantragt in ihrer Eingabe zur aufschiebenden Wirkung vom 8. Juni 2009 die Gewährung der unentgeltlichen Rechtspflege. Mit Verfügung vom 10. Juni 2009 wurde der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt. 