Sachverhalt:
A. X._ (nachfolgend Beschwerdeführer) und Y._ (nachfolgend Beschwerdegegnerin) heirateten am 2. August 2002. Sie wurden Eltern dreier Kinder (Jahrgang 2003 sowie Zwillinge mit Jahrgang 2005). Die Mutter und die Kinder verfügen über die Staatsangehörigkeit der Schweiz und von Spanien.
Auf gemeinsames Begehren der Ehegatten schied der Gerichtspräsident A._ des Gerichtskreises Z._ am 12. Juni 2009 die Ehe und regelte die Scheidungsfolgen gemäss Ehescheidungskonvention. Was die Kinderbelange betrifft, teilte der Gerichtspräsident der Mutter die elterliche Sorge über die drei Kinder zu und ordnete die Beibehaltung der Erziehungsbeistandschaft an. Er gewährte dem Vater ein Ferienrecht von vier Wochen pro Jahr und ein Besuchsrecht am ersten, zweiten und vierten Wochenende im Monat. Das dritte und ein allfälliges fünftes Wochenende im Monat verbringen die Kinder bei der Mutter. Fällt ein Kontaktwochenende ausnahmsweise aus, besteht kein Anspruch auf Kompensation (Ziff. 3 und 4 der gerichtlich genehmigten Scheidungskonvention).
B. B.a Mit Beschluss vom 23. November 2009 wies die Vormundschaftskommission der Einwohnergemeinde Z._ mehrere Anträge des Beschwerdeführers im Zusammenhang mit der Ausübung des persönlichen Verkehrs ab.
B.b Die dagegen vom Beschwerdeführer erhobene Beschwerde hiess der Regierungsstatthalter von Z._ im Entscheid vom 11. Februar 2010 teilweise gut. Soweit vorliegend massgebend, wies er die Beschwerdegegnerin an, das Besuchsrecht des Beschwerdeführers durch ihre Ferien mit den Kindern pro Jahr höchstens zwei Mal zu beschneiden. Hingegen wies er die Begehren des Beschwerdeführers ab, wonach der Beschwerdegegnerin hätte verboten werden sollen, die Kinder permanent oder unter temporärer Vereitelung des Besuchsrechts ins Ausland zu verbringen, beziehungsweise wonach Ferien mit den Kindern von mehr als vier Wochen pro Jahr und zwei Wochen am Stück nur mit seinem vorgängigen schriftlichen Einverständnis zulässig gewesen wären.
B.c Dagegen gelangten beide Parteien an das Obergericht des Kantons Bern. Dieses urteilte am 22. April 2010 unter anderem wie folgt:
Es wies die Beschwerdegegnerin unter Strafandrohung an, ihre Ferien künftig so zu gestalten, dass das Kontaktrecht der Kinder mit deren Vater nur ausnahmsweise - für das Jahr 2010 maximal drei Mal - beschnitten wird (Ziff. 3 des obergerichtlichen Dispositivs). Die beiden anderen Anträge des Beschwerdeführers wies es wie bereits der Regierungsstatthalter ab (Ziff. 4 und 5 des obergerichtlichen Urteils).
C. C.a Mit Beschwerde vom 17. Mai 2010 (Postaufgabe am selben Tag) beantragt der Beschwerdeführer dem Bundesgericht die Aufhebung der Ziff. 3 - 5 des obergerichtlichen Urteils und stellt die folgenden Begehren:
a) Die Beschwerdegegnerin sei unter Strafandrohung nach Art. 292 StGB anzuweisen, künftige Ferienbezüge so zu gestalten, dass das Kontaktrecht des Beschwerdeführers zu den gemeinsamen Kindern - vorbehältlich höherer Gewalt - nicht beschnitten wird;
b) der Beschwerdegegnerin sei unter Strafandrohung nach Art. 292 StGB zu verbieten, die gemeinsamen Kinder permanent oder unter temporärer Vereitelung des Kontaktrechts des Beschwerdeführers ins Ausland zu verbringen;
c) die Beschwerdegegnerin sei zu verpflichten, die drei gemeinsamen Kinder nicht ohne vorgängiges, schriftliches Einverständnis des Beschwerdeführers mehr als vier Wochen pro Jahr in die Ferien zu nehmen und nicht länger als zwei Wochen an einem Stück.
Der Beschwerdeführer beantragt dem Bundesgericht, die Begehren gemäss Buchstabe a) und b) als vorsorgliche Massnahme für die Dauer des Verfahrens anzuordnen. Sodann beantragt er den Ausstand von Bundesrichter von Werdt. Am 10. Juni 2010 hat er seine Beschwerde mit zwei Urkunden ergänzt.
C.b Mit Verfügung vom 19. Mai 2010 wies die Abteilungspräsidentin das Gesuch um vorsorgliche Massnahmen ab.
Es sind die Akten, aber keine Vernehmlassungen eingeholt worden. Die Beschwerdegegnerin schliesst in ihrer unaufgeforderten Stellungnahme vom 21. Juni 2010 auf Abweisung der Beschwerde, worauf der Beschwerdeführer in seiner Eingabe vom 22. Juni 2010 verlangt, diese Vernehmlassung aus den Akten zu weisen.

Erwägungen:
1. 1.1 Die Beschwerde richtet sich gegen Anweisungen an die Eltern im Zusammenhang mit der Durchführung des persönlichen Verkehrs. Ein solcher Entscheid unterliegt der Beschwerde in Zivilsachen (Art. 72 BGG). Die Beschwerde betrifft eine nicht vermögensrechtliche Angelegenheit, über die das Obergericht als letzte kantonale Instanz (Art. 75 Abs. 1 BGG) entgegen den Anträgen des Beschwerdeführers (Art. 76 Abs. 1 BGG) entschieden hat. Der obergerichtliche Entscheid schliesst das kantonale Verfahren ab (Art. 90 BGG). Auf die fristgerecht erhobene Beschwerde kann somit grundsätzlich eingetreten werden.
1.2 Der Beschwerdeführer hat seine ergänzende Eingabe vom 10. Juni 2010 (Postaufgabe am selben Tag) erst nach Ablauf der Rechtsmittelfrist von 30 Tagen (Art. 100 Abs. 1 BGG) eingereicht. Auf diese Eingabe ist nicht einzutreten.
1.3 Neue Tatsachen und Beweismittel dürfen vor Bundesgericht nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG). Die von der Beschwerdegegnerin eingereichten Beilagen betreffen einerseits ein Schreiben, das bereits anlässlich des obergerichtlichen Verfahrens Bestand hatte, aber nicht vorgebracht wurde (<ref-ruling> E. 4.4.3 S. 128 f.). Andererseits handelt es sich um eine E-Mail, die erst nach dem angefochtenen Entscheid entstanden ist (<ref-ruling> E. 5.2.4 S. 229). Diese Beweismittel sind ungeachtet des im vorliegenden Bereich geltenden Untersuchungsgrundsatzes (vgl. <ref-ruling> E. 1c S. 23) unzulässig und unbeachtlich.
2. Der Beschwerdeführer stellt ein Ausstandsbegehren gegen Bundesrichter von Werdt (Art. 36 Abs. 1 BGG). Das Begehren erweist sich als gegenstandslos, da dieser nicht am vorliegenden Verfahren mitwirkt.
3. Nachfolgend ist zunächst auf die Rechtsnatur der strittigen Anordnungen einzugehen (E. 4). Dann sind die Rügen im Zusammenhang mit der Frage zu beurteilen, ob es der Beschwerdegegnerin zusteht, mit den Kindern längere Ferien zu verbringen, wenn damit das Besuchsrecht des Vaters beschnitten wird (E. 5). Schliesslich wendet sich der Beschwerdeführer gegen Auslandsaufenthalte der Beschwerdegegnerin (E. 6).
4. 4.1 Der Beschwerdeführer macht geltend, aufgrund der Regelung des Obergerichts, wonach der Beschwerdegegnerin ausnahmsweise erlaubt werde, sein Besuchsrecht zu beschneiden, werde im Ergebnis ohne Vorliegen der entsprechenden Voraussetzungen das Scheidungsurteil abgeändert (S. 7 ff. der Beschwerde).
4.2 Für die Voraussetzungen einer Änderung des Anspruchs auf persönlichen Verkehr verweist Art. 134 Abs. 2 ZGB auf die Bestimmungen über die Wirkungen des Kindesverhältnisses (Art. 273 und 274 ZGB). Nötig ist eine wesentliche Veränderung der Verhältnisse, die eine Abänderung der im Scheidungsurteil getroffenen Ordnung im Interesse des Kindes zwingend erfordert (<ref-ruling> E. 1 S. 77 f.).
4.3 Der Beschwerdeführer legt nicht dar und es ist auch nicht ersichtlich, inwiefern die Regelung des Besuchsrechts (erstes, zweites und viertes Wochenende im Monat) und das Ferienrecht des Vaters (vier Wochen pro Jahr) im angefochtenen Entscheid abgeändert worden sein soll. Vielmehr hat diese Regelung nach wie vor Gültigkeit und wird beibehalten. Die obergerichtliche Anordnung betrifft einzig die Handhabung und damit die konkrete Ausübung dieser Regelung. Weder handelt es sich damit um eine vom Beschwerdeführer (auch) behauptete erstmalige Regelung des persönlichen Verkehrs, noch um ein Abänderungsverfahren nach Art. 134 ZGB.
Soweit der Beschwerdeführer diesbezüglich weiter rügt, die Vormundschaftsbehörde sei für die Abänderung eines Scheidungsurteiles im Übrigen nicht zuständig, wäre auch diese Rüge unbegründet. Gemäss Art. 134 Abs. 4 ZGB ist die Vormundschaftsbehörde - wie vorliegend - ausserhalb eines gerichtlichen Verfahrens für die Änderung des persönlichen Verkehrs zuständig.
4.4 Die strittigen Anordnungen sind unter Art. 273 Abs. 2 ZGB zu erfassen. Nach dieser Bestimmung kann die Vormundschaftsbehörde Eltern ermahnen und ihnen Weisungen erteilen, wenn sich die Ausübung oder Nichtausübung des persönlichen Verkehrs für das Kind nachteilig auswirkt oder wenn eine Ermahnung oder eine Weisung aus anderen Gründen geboten ist. Diese Norm ist damit gerade auf Fälle zugeschnitten, wo Schwierigkeiten in der Ausübung des persönlichen Verkehrs bestehen.
5. 5.1 Das Obergericht wies die Beschwerdegegnerin unter Strafandrohung gemäss Art. 292 StGB an, das Besuchsrecht des Beschwerdeführers nur ausnahmsweise, für das Jahr 2010 maximal drei Mal, zu beschneiden (Ziff. 3 des Dispositivs des angefochtenen Entscheides). Es wies zudem das Begehren ab, wonach die Beschwerdegegnerin bei Ferien von mehr als vier Wochen pro Jahr beziehungsweise zwei Wochen am Stück vorgängig das schriftliche Einverständnis des Beschwerdeführers hätte einholen müssen (Ziff. 5 des Dispositivs des angefochtenen Entscheides).
Es hielt dazu fest, der Umfang des Anspruchs auf Ferien der sorgeberechtigten Person werde in der Gerichtspraxis zwar normalerweise nicht geregelt. Dies bedeute jedoch nicht, dass die Sorgerechtsinhaberin nicht ebenso ein gemeinsames Recht auf Ferien mit den Kindern habe wie der andere Elternteil. Gestehe man vorliegend der Beschwerdegegnerin Ferien im Umfang des Ferienrechts des Beschwerdeführers (vier Wochen) zu, seien Überschneidungen mit dessen ausgedehntem Besuchsrecht nicht zu vermeiden. Der Beschwerdegegnerin sei es deshalb unter Vorbehalt des Missbrauchs erlaubt, das Besuchsrecht des Beschwerdeführers unter gewissen Umständen zu beschneiden. Damit die Beschwerdegegnerin pro Jahr zwei Wochen am Stück und zusätzlich eine ganze Woche Ferien mit ihren Kindern verbringen könne (jeweils ab Samstag), müsse ihr konkret ermöglicht werden, das Besuchsrecht des Beschwerdeführers jährlich drei Mal und nicht mehr als zwei Mal pro Monat zu beschneiden (S. 17 ff. des angefochtenen Entscheides).
5.2 Der Beschwerdeführer bringt dagegen vor, ihm gehe es (auch mit seinem Antrag auf vorgängige Einholung seiner Zustimmung) einzig um den wirksamen Vollzug und die Wahrung des in der Scheidungskonvention vereinbarten Besuchsrechts. Die Vollziehung dieses in der Konvention festgehaltenen väterlichen Kontaktrechts sei Aufgabe der Vormundschaftsbehörde. Der persönliche Verkehr bedürfe einer dauerhaften und stabilen Ordnung, um der Entfremdung der Kinder entgegenzuwirken. Deshalb müsse die Scheidungskonvention eingehalten werden. Das Vorgehen des Obergerichts verletze Art. 273 ZGB, da es sein Besuchsrecht aushöhle (S. 7 - 11 und 14 f. der Beschwerde).
5.2 Der Beschwerdeführer bringt dagegen vor, ihm gehe es (auch mit seinem Antrag auf vorgängige Einholung seiner Zustimmung) einzig um den wirksamen Vollzug und die Wahrung des in der Scheidungskonvention vereinbarten Besuchsrechts. Die Vollziehung dieses in der Konvention festgehaltenen väterlichen Kontaktrechts sei Aufgabe der Vormundschaftsbehörde. Der persönliche Verkehr bedürfe einer dauerhaften und stabilen Ordnung, um der Entfremdung der Kinder entgegenzuwirken. Deshalb müsse die Scheidungskonvention eingehalten werden. Das Vorgehen des Obergerichts verletze Art. 273 ZGB, da es sein Besuchsrecht aushöhle (S. 7 - 11 und 14 f. der Beschwerde).
5.3 5.3.1 Wie bei der Regelung des persönlichen Verkehrs allgemein (<ref-ruling> E. 3 S. 210 mit Hinweisen) und aufgrund der Kann-Vorschrift in Art. 273 Abs. 2 ZGB im Besonderen kommt dem Richter und der Behörde ein grosser Ermessensspielraum zu. Das Bundesgericht überprüft die Ausübung richterlichen Ermessens durch die letzte kantonale Instanz mit Zurückhaltung; es schreitet nur dann ein, wenn grundlos von den in Lehre und Rechtsprechung entwickelten Grundsätzen abgewichen wird, wenn Tatsachen berücksichtigt werden, die keine Rolle hätten spielen dürfen, oder wenn umgekehrt Umstände ausser Betracht geblieben sind, die zwingend hätten beachtet werden müssen (<ref-ruling> E. 2.1 S. 51).
5.3.2 Nach Art. 273 Abs. 1 ZGB haben Eltern, denen die elterliche Sorge oder Obhut nicht zusteht, und das unmündige Kind gegenseitig Anspruch auf angemessenen persönlichen Verkehr. Als oberste Richtschnur für die Ausgestaltung (und Ausübung) des persönlichen Verkehrs gilt das Kindeswohl, das anhand der Umstände des konkreten Einzelfalls zu beurteilen ist, wobei allfällige Interessen der Eltern zurückzutreten haben (<ref-ruling> E. 2.1 S. 587 f.). Der Sicherung des Kindeswohls dienen die Weisungen im Sinne von Art. 273 Abs. 2 ZGB.
5.3.3 Ob es dem sorgeberechtigten Elternteil möglich sein muss, Ferien mit seinen Kindern zu verbringen, die länger dauern, als das Intervall zwischen den ordentlichen Besuchstagen, ist gesetzlich nicht geregelt.
In der Lehre wird festgehalten, von der Einhaltung der Besuchsordnung dürfe einseitig nur aus wichtigen Gründen abgewichen werden. Darunter fielen jedoch nicht Anlässe, deren Daten der Besuchsberechtigte, der Inhaber der elterlichen Sorge oder das Kind (mit-) bestimmen könnten. Auszunehmen davon seien jedoch Ferien, die länger dauerten als das Intervall zwischen den ordentlichen Besuchstagen (HEGNAUER, Berner Kommentar, 1997, N. 128 zu Art. 273 ZGB; implizit und allgemein die Beschneidung des Besuchsrechts zwecks Ferien bejahend: BLUM, Der persönliche Verkehr mit dem unmündigen Kind, 1983, S. 80 f.; MEIER/STETTLER, Droit de la filiation, 4. Aufl. 2009, N. 708; HAMMER-FELDGES, Persönlicher Verkehr - Probleme der Rechtsanwendung für Vormundschaftsbehörden, Richter und Anwälte, in: ZVW 1993, S. 24). Auch das Bundesgericht ging im nicht publizierten Urteil 5C.146/2001 vom 26. Oktober 2001 E. 2a, in: FamPra.ch 2002 S. 399 implizit davon aus, dass durch Ferien des Sorgeberechtigten das Besuchsrecht beschnitten werden kann.
5.3.4 Es entbehrt nicht einer gewissen Selbstverständlichkeit, dass die sorgeberechtigte Mutter einen Anspruch darauf hat, Ferien mit ihren Kindern zu verbringen. Bei einem - wie vorliegend - ausgedehnten Besuchsrecht des Vaters lässt es sich dabei nicht verhindern, dass Besuchstage ausfallen. Die Ferienplanung der Sorgeberechtigten steht aber unter dem Vorbehalt des Rechtsmissbrauchs und der Ausfall von Besuchswochenenden muss die Ausnahme bleiben.
Damit ist es nicht zu beanstanden, wenn die Vorinstanz der sorgeberechtigten Beschwerdegegnerin zugestanden hat, ausnahmsweise aufgrund ihrer Ferienabwesenheit (jeweils für Ferien von zwei Wochen und einer Woche am Stück, gerechnet von Samstag bis Samstag) das Besuchsrecht des Beschwerdeführers zu beschneiden. Diese Regelung steht auch im Einklang mit Ziff. 4 der gerichtlich genehmigten Scheidungskonvention, die (zur Regelung der Nachholung) vorsieht, dass die Kontaktwochenenden nur ausnahmsweise auszufallen haben. Dass damit, wie vom Beschwerdeführer behauptet, einzig Fälle höherer Gewalt gemeint sein sollen, lässt sich dieser Regelung nicht entnehmen.
Damit ist es nicht zu beanstanden, wenn die Vorinstanz der sorgeberechtigten Beschwerdegegnerin zugestanden hat, ausnahmsweise aufgrund ihrer Ferienabwesenheit (jeweils für Ferien von zwei Wochen und einer Woche am Stück, gerechnet von Samstag bis Samstag) das Besuchsrecht des Beschwerdeführers zu beschneiden. Diese Regelung steht auch im Einklang mit Ziff. 4 der gerichtlich genehmigten Scheidungskonvention, die (zur Regelung der Nachholung) vorsieht, dass die Kontaktwochenenden nur ausnahmsweise auszufallen haben. Dass damit, wie vom Beschwerdeführer behauptet, einzig Fälle höherer Gewalt gemeint sein sollen, lässt sich dieser Regelung nicht entnehmen.
5.4 5.4.1 Damit stellt sich die Frage, ob ausgefallene Besuchswochenenden des Beschwerdeführers zu kompensieren sind. Ob und in welchem Umfang ausgefallene Besuchstage nachgeholt werden können, ist gesetzlich ebenfalls nicht geregelt. Das Obergericht lehnte eine Kompensation unter Verweis auf die entsprechende Regelung der Parteien in der Scheidungskonvention ab (S. 19 des angefochtenen Entscheides).
5.4.2 Das Nachholen von Besuchen soll nicht zu einer unangemessenen Häufung führen. Anspruch und Erfüllung des persönlichen Verkehrs sind nicht gleichsam buchhalterisch auszugleichen, sondern es ist ein angemessener Kontakt zwischen dem besuchsberechtigten Elternteil und dem Kind zu gewährleisten (Urteile 5P.10/2002 vom 16. Juli 2002 E. 2, in: FamPra.ch 2002 S. 834 f.; 5C.146/2001 vom 26. Oktober 2001 E. 2a, in: FamPra.ch 2002 S. 399, jeweils mit Hinweisen). Die Meinungen in der Lehre über die Frage der Kompensation im Falle von Ferien des Sorgeberechtigten sind geteilt. Einige Autoren sprechen sich für die Nachholung aus (HEGNAUER, a.a.O., N. 131 zu Art. 273 ZGB), andere verneinen einen Nachholanspruch (Blum, a.a.O., S. 80 f.; HAMMER-FELDGES, a.a.O., S. 24; gleicher Meinung anscheinend Wirz, in: FamKommentar Scheidung, 2005, N. 26 zu Art. 273 ZGB; differenzierend MEIER/STETTLER, a.a.O., N. 708 mit Verweis auf SJZ 1996, S. 298, wonach kein Nachholanspruch besteht, wenn der nicht Sorgeberechtigte sein eigenes Ferienrecht während einem gewichtigen Teil der Ferien der Kinder ausüben konnte).
5.4.3 Vorliegend haben die Parteien in Ziff. 4 ihrer Scheidungskonvention vereinbart, dass ausnahmsweise ausgefallene Kontaktwochenenden nicht zu kompensieren sind. Angesichts der uneinheitlichen Meinungen zur Kompensation bei Ferien einerseits und der klaren Regelung in der Scheidungskonvention der Parteien andererseits, ist der Ermessensentscheid des Obergerichts, die ausfallenden Wochenenden nicht zu kompensieren, nicht zu beanstanden.
5.5 Die obergerichtliche Regelung gemäss Ziff. 3 des angefochtenen Urteilsdispositivs und die Ablehnung des Begehrens um vorgängige Einholung der Zustimmung des Beschwerdeführers bei Ferien der Beschwerdegegnerin (Ziff. 5 des Dispositivs) ist damit nicht zu beanstanden.
6. 6.1 Das Obergericht wies im angefochtenen Entscheid die Begehren des Beschwerdeführers ab, der Beschwerdegegnerin unter Strafandrohung zu verbieten, die gemeinsamen Kinder permanent oder unter temporärer Vereitelung des Besuchsrechts ins Ausland zu verbringen (Ziff. 4 des Dispositivs des angefochtenen Entscheides).
Es hielt dazu fest, die elterliche Sorge umfasse auch das Recht, den Aufenthaltsort des Kindes zu bestimmen. Damit könne die Beschwerdegegnerin grundsätzlich jederzeit mit ihren Kindern ins Ausland reisen (S. 20 des angefochtenen Entscheides).
6.2 Der Beschwerdeführer rügt, durch die Ablehnung seines Antrages auf Erlass einer Weisung im Zusammenhang mit Auslandsaufenthalten der Beschwerdegegnerin werde Art. 273 Abs. 2 ZGB verletzt. Werde ihr erlaubt, mit den Kindern nach Spanien zu reisen und dort permanent oder doch zumindest für längere Zeit einen Aufenthalt zu begründen, werde dadurch das Kontaktrecht des Vaters faktisch vereitelt, womit Art. 21 des Haager Übereinkommens vom 25. Oktober 1980 über die zivilrechtlichen Aspekte internationaler Kindesentführungen (HKÜ; SR 0.211.230.02) verletzt werde.
6.3 Das HKÜ bezweckt, die sofortige Rückgabe widerrechtlich in einen Vertragsstaat verbrachter oder dort zurückgehaltener Kinder sicherzustellen und zu gewährleisten, dass das in einem Vertragsstaat bestehende Sorge- und Besuchsrecht in den anderen Vertragsstaaten tatsächlich beachtet wird (Art. 1 HKÜ). Letzterem dient die vom Beschwerdeführer angerufene Norm von Art. 21 HKÜ, die sicherstellen will, dass die Ausübung des Besuchsrechts in einem anderen Vertragsstaat (in dem sich das Kind befindet) gewährleistet wird (vgl. PIRRUNG, in: Staudingers Kommentar zum BGB, 2009, Vorbem. zu Art. 19 EGBGB, D. 90).
Da vorliegend jedoch nur ein Vertragsstaat involviert ist, fehlt es an der Internationalität des Sachverhalts und damit der Anwendbarkeit des HKÜ (Zürcher, Kindesentführung und Kindesrechte, 2005, S. 4). Die Kinder haben ihren gewöhnlichen Aufenthalt in der Schweiz und gemäss den obergerichtlichen Tatsachenfeststellungen, die für das Bundesgericht verbindlich sind und vom Beschwerdeführer nicht bestritten werden (Art. 105 Abs. 1 und 2 BGG), ist auch keine Verlegung in das Ausland geplant (S. 22 des angefochtenen Entscheides).
6.4 Was die Rüge der Verletzung von Art. 273 Abs. 2 ZGB betrifft, ist nicht ersichtlich, worin diese liegen könnte. Der Beschwerdeführer wendet sich (vgl. E. 6.3 oben) nicht gegen die vorinstanzliche Beweiswürdigung, wonach der Wille der Beschwerdegegnerin zum Wegzug in ein anderes Land und damit eine Entführungsgefahr nicht gegeben ist. Sofern er geltend macht, es seien der Beschwerdegegnerin allgemein Auslandsaufenthalte zu verbieten, da dies zur Vereitelung seines Besuchsrechts führe, verkennt er, dass das Obhutsrecht als Teil der elterlichen Sorge die Befugnis umfasst, den Aufenthaltsort des Kindes zu bestimmen und damit mit den Kindern wegzuziehen, namentlich auch ins Ausland. Diese Befugnis findet ihre Grenzen im Rechtsmissbrauch (z.B. Wegzug ohne plausible Gründe oder einzig zur Vereitelung von Kontakten zwischen Kind und Elternteil; BGE 5D_171/2009 vom 1. Juni 2010 E. 3.2 und 3.3). Vorliegend ist kein rechtsmissbräuchliches Vorgehen ersichtlich, hat doch das Obergericht festgestellt (was vom Beschwerdeführer nicht bestritten wird), dass die Beschwerdegegnerin das Besuchsrecht des Beschwerdeführers im Jahr 2010 noch kein einziges Mal beschnitten hat. Die Tatsache allein, dass mit einem allfällig auch längeren Wegzug das Besuchsrecht des anderen Elternteils faktisch erschwert wird, ist für sich allein noch kein Grund, dem obhutsberechtigten Ehegatten den Wegzug ins Ausland zu verbieten (BGE 5D_171/2009 vom 1. Juni 2010 E. 3.3).
Die Abweisung des Begehrens um Erlass dieser Weisung durch das Obergericht (Ziff. 5 des angefochtenen Entscheides) ist damit nicht zu beanstanden.
7. Aus den dargelegten Gründen muss die Beschwerde abgewiesen werden, soweit darauf einzutreten ist. Der Beschwerdeführer wird damit kostenpflichtig (Art. 66 Abs. 1 BGG). Eine Parteientschädigung ist nicht zu sprechen, da weder zum Gesuch um Erlass vorsorglicher Massnahmen noch in der Sache eine Vernehmlassung eingeholt wurde und die Stellungnahme der Beschwerdegegnerin vom 21. Juni 2010 unaufgefordert erfolgt ist.

Demnach erkennt das Bundesgericht:
1. Das Ausstandsbegehren gegen Bundesrichter von Werdt wird als gegenstandslos abgeschrieben.
2. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
3. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien, der Einwohnergemeinde Z._ und dem Obergericht des Kantons Bern, Appellationshof, 1. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 21. Juli 2010
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Bettler