Sachverhalt:
A. X._ und Z._ sind die Kinder von A._ und B._. Y._ ist die Ehefrau von X._. A._ verstarb am 16. August 1993 in Monaco, wo er zusammen mit seiner Ehefrau seit 1987 in einer Wohnung im Haus C._ lebte. Seine Ehefrau beerbte ihn. Nach einem Unfall 1994 verblieb sie bis zu ihrem Tode am 20. Juli 2000 in Griechenland. Gemäss Testament von B._ (fortan: Erblasserin) aus dem Jahre 1996 sollen ihre Kinder zu gleichen Teilen erben.
Nachdem die Parteien bereits 2004 einen Prozess um die Herausgabe von Buchhaltungsunterlagen geführt hatten, erhob Z._ am 17. Januar 2007 gegen X._ und Y._ sowie den ehemaligen Anwalt der Erblasserin Forderungsklage in Monaco. Darin wirft sie ihrem Bruder und ihrer Schwägerin im Wesentlichen vor, die Wohnung im Haus C._ in Monaco widerrechtlich und ohne Bezahlung von Mietzinsen und Nebenkosten bewohnt zu haben. Des Weiteren sei diverses Mobiliar der Erblasserin nicht geteilt worden und ihr Bruder habe widerrechtlich Kontobezüge vorgenommen und Gelder der Erblasserin unterschlagen.
B. B.a Auf Ersuchen von Z._ erliess der Gerichtspräsident 1 des Gerichtskreises XIII Obersimmental-Saanen am 9. Februar 2007 gestützt auf Art. 271 Abs. 1 Ziff. 4 SchKG einen Arrestbefehl gegen X._ und Y._ über eine Forderung von Fr. 8'002'221.- nebst Zins zu 5 % seit dem 19. Oktober 2003. Die beiden Arreste (Nr. 1 gegen X._ und Nr. 2 gegen Y._) wurden am 12. Februar 2007 durch das Betreibungsamt Berner Oberland, Dienststelle Obersimmental-Saanen, vollzogen. Arrestgegenstände sind Grundstücke und diverse in der Wohnung des Ehepaars X._/ Y._ befindliche Vermögensobjekte.
B.b Gegen die Arrestbefehle erhoben X._ und Y._ am 12. März 2007 Einsprache, woraufhin der Gerichtspräsident 1 des Gerichtskreises XIII Obersimmental-Saanen die Arrestforderung am 3. Mai 2007 auf Fr. 2'723'230.-- reduzierte.
C. C.a Auf Appellation von Z._ hin wies das Obergericht des Kantons Bern mit Entscheid vom 17. August 2007 die Einsprachen wegen Verspätung zurück. Dieser Entscheid wurde vom Bundesgericht mit Urteil vom 9. Januar 2009 (5A_545/2007; teilweise publiziert in <ref-ruling>) aufgehoben und die Sache zur Behandlung der Einsprachen an die Vorinstanz zurückgewiesen.
C.b Das Obergericht hiess mit Entscheid vom 21. September 2009 die Einsprachen teilweise gut und reduzierte die Arrestforderung auf Fr. 5'456'006.05.
D. X._ und Y._ (fortan: Beschwerdeführer) haben gegen diesen Entscheid am 26. Oktober 2009 Beschwerde in Zivilsachen ergriffen. Sie beantragen die Aufhebung des angefochtenen Entscheids sowie die Abweisung der Appellation von Z._ (fortan: Beschwerdegegnerin), eventualiter die Bestätigung des Entscheids des Gerichtspräsidenten vom 3. Mai 2009 (recte: 2007).
Es sind keine Vernehmlassungen eingeholt worden.

Erwägungen:
1. 1.1 Angefochten ist ein letztinstanzlicher Entscheid (Art. 75 Abs. 1 BGG; LEUCH UND ANDERE, Die Zivilprozessordnung für den Kanton Bern, 5. Aufl. 2000, N. 1a zu Art. 314 ZPO) über eine Schuldbetreibungs- und Konkurssache. Eine solche kann mit Beschwerde in Zivilsachen an das Bundesgericht weitergezogen werden (Art. 72 Abs. 2 lit. a BGG). Der erforderliche Streitwert von Fr. 30'000.-- ist bei weitem überschritten (Art. 74 Abs. 1 lit. b BGG). Die Beschwerde ist fristgerecht erfolgt (Art. 100 Abs. 1 i.V.m. Art. 45 Abs. 1 BGG).
1.2 Dem angefochtenen Entscheid liegt eine Weiterziehung (Art. 278 Abs. 3 SchKG) des Einspracheentscheides gegen den Arrestbefehl (Art. 278 Abs. 1 und 2 SchKG) zugrunde. Der Weiterziehungsentscheid beschlägt ausschliesslich das betreffende Arrestverfahren und befindet ebenso wenig wie der Arrest selbst endgültig über Bestand und Fälligkeit der Arrestforderung. Er gilt damit wie der Arrestentscheid (<ref-ruling> E. 1 S. 590 f.) als vorsorgliche Massnahme im Sinn von Art. 98 BGG (<ref-ruling> E. 1.2 S. 234 mit Hinweis). Folglich kann vorliegend einzig die Verletzung verfassungsmässiger Rechte gerügt werden, die das Bundesgericht nur insofern prüft, als eine entsprechende Rüge in der Beschwerde vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG). Dabei muss klar und detailliert anhand der Erwägungen des angefochtenen Entscheides dargelegt werden, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-ruling> E. 6 S. 397 mit Hinweis). Wird eine Verletzung des Willkürverbots - einschliesslich der Willkür bei der Sachverhaltsfeststellung (<ref-ruling> E. 1.4.3 S. 255) - geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen aufgezeigt werden, in welcher Hinsicht der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246 mit Hinweis). Auf rein appellatorische Kritik am angefochtenen Entscheid ist nicht einzutreten (<ref-ruling> E. 3.1 S. 399; <ref-ruling> E. 2 S. 591 f.).
2. 2.1 Das Obergericht hat festgestellt, die Erblasserin habe ihren letzten Wohnsitz in Monaco gehabt und sei kanadische und griechische Staatsangehörige gewesen. Unter Bezugnahme auf Art. 91 Abs. 1 IPRG (SR 291) und das Kollisionsrecht Monacos hat es als glaubhaft erachtet, dass auf die Arrestforderungen monegassisches Recht anwendbar sei. Art. 673 des monegassischen Zivilgesetzbuches sehe vor, dass der Erbe, der Erbschaftsgegenstände unterschlagen bzw. vorenthalten habe, seinen Anspruch auf ebendiese Gegenstände verliere (Erbhehlerei). Der Beschwerdeführer 1 habe deshalb bezüglich der nachfolgend genannten Werte und Gegenstände seine Ansprüche verloren, womit der Beschwerdegegnerin nicht bloss die Hälfte derselben, sondern der volle Betrag zustehe. Obschon nicht Erbin, sei auch die Beschwerdeführerin 2 passivlegitimiert. Zur Verrechnung gestellte Gegenforderungen der Beschwerdeführer könnten mangels liquiden Nachweises durch Urkunden im Einspracheverfahren nicht berücksichtigt werden.
2.2 In Bezug auf die geltend gemachten Arrestforderungen hat die Vorinstanz die Darstellung der Beschwerdegegnerin als grundsätzlich glaubhafter erachtet als diejenige der Beschwerdeführer. Im Einzelnen hat sie dabei das nachfolgend Zusammengefasste erwogen.
2.2.1 Zunächst sei eine Ersatzforderung der Beschwerdegegnerin über insgesamt EUR 568'009.18 (recte: EUR 568'006.18) - umgerechnet Fr. 916'960.80 - glaubhaft gemacht, da die Beschwerdeführer seit 1998 unrechtmässig die Wohnung C._ in Monaco bewohnt und dafür weder die Miete noch die Nebenkosten (Elektrizität, Wasser, Telefon, Lohn des Chauffeurs) bezahlt hätten. Unbestritten sei, dass die entsprechenden Zahlungen von Kontos der Erblasserin erfolgt seien, die Beschwerdeführer 1998 Wohnsitz in Monaco begründet hätten und der Mietvertrag per März 1998 auf den Beschwerdeführer 1 überschrieben worden sei. Die Beschwerdeführer bestritten hingegen, die Wohnung benutzt zu haben, hätten aber einzig nachweisen können, in der betreffenden Zeit fünf Nächte in einem Hotel in Monaco verbracht zu haben. Da keine plausible Begründung vorliege, wo sie sich in der fraglichen Zeit sonst aufgehalten hätten, sei die Benutzung der Wohnung glaubhaft, zumal die angefallenen Nebenkosten auf eine Benutzung der Wohnung schliessen liessen.
2.2.2 Die Vorinstanz hat des Weiteren erkannt, es seien Vermögensgegenstände aus der Wohnung C._ im Gesamtwert von EUR 1'230'000.-- (Fr. 1'985'650.50) unter den Erben zu teilen. Ein behauptetes Alleineigentumsrecht der Beschwerdegegnerin an Objekten im Wert von EUR 230'000.-- habe diese aber nicht glaubhaft machen können. Ebenso hält die Vorinstanz dafür, die im griechischen Haus der Erblasserin vorhandenen Wertgegenstände (ca. EUR 775'000.--, Fr. 1'251'121.25) müssten hälftig geteilt werden. Aufgrund von Art. 673 des monegassischen Zivilgesetzbuches stehe der Beschwerdegegnerin aber nicht nur ein hälftiger, sondern ein Anspruch auf den vollen geltend gemachten Wert zu (vgl. oben E. 2.1).
2.2.3 In einem weiteren Punkt hat die Vorinstanz festgehalten, zwischen den Parteien sei unbestritten vereinbart worden, der Erblasserin jährlich USD 540'000.-- für ihren Lebensunterhalt und die medizinische Betreuung auf ein Konto bei der Bank H._ in Athen zu überweisen. Insgesamt seien USD 2'441'000.-- überwiesen worden. Streitig sei, ob der Beschwerdeführer 1 diese Gelder unterschlagen habe. Gemäss Vorinstanz habe der Beschwerdeführer 1 Zugriff auf das erwähnte Konto seiner Mutter gehabt. Die von ihm eingereichten Kontoauszüge liessen keine Rückschlüsse auf die Verwendung der Gelder zu. Die Vorinstanz hat in der Folge als glaubhaft erachtet, dass der Beschwerdeführer 1 die Hälfte der Summe unterschlagen habe, während die andere Hälfte für die Erblasserin verwendet worden sei, und hat die zu verarrestierende Forderung demnach umgerechnet auf Fr. 1'302'273.50 festgesetzt.
2.2.4 Unklar bleibt die obergerichtliche Beurteilung des Verbleibs von EUR 16'241.42 (Fr. 26'219.35), die vom Konto der Bank I._ Monaco abgehoben worden sein sollen. Die entsprechende Summe taucht jedenfalls in der Schlusszusammenstellung der Arrestforderungen nicht mehr auf. Ein diesbezügliches Versehen der Vorinstanz wirkt sich aber einzig zulasten der Beschwerdegegnerin aus. Auf die Ausführungen der Beschwerdeführer im Hinblick auf diesen Posten ist deshalb mangels Rechtsschutzinteresses nicht einzutreten.
2.3 Das Obergericht hat in der Folge erkannt, es seien insgesamt Vermögensgegenstände für Forderungen in der Höhe von Fr. 5'456'006.05 gestützt auf Art. 271 Abs. 1 Ziff. 4 SchKG zu verarrestieren.
3. Die Beschwerdeführer wenden sich zunächst in verschiedener Hinsicht gegen den vorinstanzlich als glaubhaft erachteten Sachverhalt. Sie wiederholen dabei ausführlich und zu einem grossen Teil wortwörtlich ihre Sachverhaltsdarstellung aus der Arresteinsprache. Es fehlt somit eine Auseinandersetzung mit den Erwägungen der Vorinstanz und des Gerichtspräsidenten, auf welche das Obergericht mehrfach verweist. Den eingangs dargestellten Begründungsanforderungen genügt dies nicht, weshalb auf die entsprechenden Vorbringen nicht eingetreten werden kann (<ref-ruling> E. 2.3 S. 247). Sie erscheinen als rein appellatorische Kritik an den vorinstanzlichen Feststellungen. Kein Zusammenhang mit bestimmten Erwägungen der Vorinstanz ist insbesondere dort ersichtlich, wo die Beschwerdeführer in Wiederholung ihrer Arresteinsprache Punkte aufwerfen, welche das Obergericht bereits zu ihren Gunsten entschieden oder welche es ohne negative Wirkung für sie offen gelassen hat. Dies trifft namentlich auf die Frage der Echtheit gewisser Unterschriften sowie des Alleineigentums der Beschwerdegegnerin an bestimmten Objekten zu (zu Letzterem E. 2.2.2).
3.1 Im Einzelnen machen die Beschwerdeführer weiterhin geltend, die Wohnung im Haus C._ bis 2006 nie selber benutzt zu haben. Die Beschwerdegegnerin habe keine handfesten Beweise für ihre Darstellung geliefert, während sie die Behauptungen der Beschwerdegegnerin widerlegt hätten.
3.2 Abgesehen von der appellatorischen Wiederholung ihrer bereits in der Arresteinsprache dargelegten Sachverhaltssicht fehlt jegliche inhaltliche Auseinandersetzung mit den tragenden vorinstanzlichen Elementen der Beweiswürdigung und damit eine rechtsgenüglich erhobene Verfassungsrüge. Die Beschwerdeführer legen nicht dar, inwiefern die Vorinstanz eine willkürliche Beweiswürdigung vorgenommen hat. Auf die entsprechenden Rügen ist nicht einzutreten.
3.3 Die Beschwerdeführer anerkennen den Anspruch der Beschwerdegegnerin auf hälftige Teilung der Fahrhabe in Monaco, bestreiten jedoch den Wert der Objekte. In ähnlicher Weise bestreiten sie zwar nicht den Teilungsanspruch bezüglich des Mobiliars in der Athener Wohnung, offenbar aber den Wert der Gegenstände. Im Hinblick auf den letztgenannten Posten rügen die Beschwerdeführer zudem sinngemäss eine mangelnde Begründung durch die Vorinstanz und damit eine Verletzung des rechtlichen Gehörs.
3.4 Soweit die wiederum weitgehend der Arresteinsprache entnommenen Ausführungen überhaupt als Auseinandersetzung mit den vorinstanzlichen Erwägungen gelesen werden könnten, beschränken sie sich auf eine appellatorische Kritik an der Beweiswürdigung, indem insbesondere die Glaubwürdigkeit verschiedener Zeugenauskünfte über die vorhandene oder einst vorhanden gewesene Fahrnis bezweifelt wird. Damit zeigen die Beschwerdeführer jedoch nicht auf, inwiefern die Beurteilung der Vorinstanzen willkürlich erfolgt sein soll. Hinsichtlich des Athener Mobiliars sind schliesslich weder die Behauptung, die Beschwerdegegnerin habe in der Steuererklärung die Gegenstände als Nonvaleur angeführt, noch die angebliche mangelnde Bereitschaft zu Verhandlungen geeignet, die Beurteilung der Vorinstanzen als willkürlich darzutun. Darauf ist nicht einzutreten.
Zu Unrecht rügen die Beschwerdeführer eine mangelnde Begründung hinsichtlich des Wertes des Athener Mobiliars. Die Ausführungen des Obergerichts sind zwar knapp, doch verweist es im ganzen betroffenen Absatz auf das Urteil des Gerichtspräsidenten. Dieser hat die Schätzung der Beschwerdegegnerin gestützt auf eine Zeugenauskunft für glaubhaft befunden. Gemäss bundesgerichtlicher Rechtsprechung muss eine Begründung so abgefasst sein, dass sich der Betroffene über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann (<ref-ruling> E. 4.1 S. 88 mit weiteren Hinweisen). Dieser Anforderung ist die Vorinstanz nachgekommen.
3.5 Die Beschwerdeführer bestreiten, sie hätten zum Lebensunterhalt und zur medizinischen Versorgung der Erblasserin bestimmte Gelder unterschlagen. Die Vorinstanz lege weder dar, wie sie zu dieser Annahme komme, noch habe sie die Höhe des Eigenbedarfs der Erblasserin genügend begründet.
3.6 Soweit die Beschwerdeführer nicht in appellatorischer Weise ihre früheren Ausführungen wiederholen, worauf nicht einzutreten ist, kritisieren sie mit der Gehörsrüge die Sachverhaltsfeststellungen der Vorinstanz. Diese hat aber entgegen der Darstellung der Beschwerdeführer erörtert, weshalb sie die Unterschlagung der Vermögenswerte als glaubhaft erachtet hat. Nach diesem grundsätzlichen Schluss ist sie zugunsten der Beschwerdeführer davon ausgegangen, dass angesichts des Lebensstandards der Familie immerhin die Hälfte des Betrags tatsächlich für den Lebensunterhalt und die medizinische Versorgung der Erblasserin verwendet worden sein dürfte. Damit ist sie - soweit dies in einem Summarverfahren und im Rahmen einer Schätzung überhaupt möglich ist - ihrer Begründungspflicht genügend nachgekommen.
3.7 Zusammenfassend erweisen sich die Einwände der Beschwerdeführer gegen die Glaubhaftmachung der Arrestforderung als unbegründet, soweit auf diese überhaupt eingetreten werden kann.
4. 4.1 Die Beschwerdeführer bestreiten, dass auf die Arrestforderungen monegassisches Recht, insbesondere Art. 673 des monegassischen Zivilgesetzbuches, anwendbar ist, wie die Vorinstanz, gestützt auf ein Gutachten von Prof. K._, Paris, angenommen hat. Die Beschwerdeführer reichen neu zwei Gegengutachten von Prof. M._, Paris, sowie Prof. N._, Athen, vom November 2008 ein, aus denen sich ergebe, dass griechisches Recht anwendbar sei. Im Ergebnis leiten sie aus der behaupteten Unanwendbarkeit von Art. 673 des monegassischen Zivilgesetzbuches ab, dass der Beschwerdeführer 1 seine Erbansprüche hinsichtlich der umstrittenen Objekte nicht verloren habe.
4.2 Die Beschwerdeführer bezeichnen die beiden neu eingereichten Rechtsgutachten als integralen Bestandteil ihrer Beschwerde. Dies widerspricht dem Grundsatz, dass die Begründung in der Beschwerdeschrift selber enthalten sein sollte (vgl. <ref-ruling> E. 3.1 S. 400; Urteil 5A_472/2009 vom 10. November 2009 E. 2.7). Es kann hier jedoch offen bleiben, ob ein solcher Verweis auf die beigelegten Schriften Dritter den Begründungsanforderungen von Art. 106 Abs. 2 BGG genügt, da die eingereichten Gutachten selbst bei ihrer Berücksichtigung nicht aufzeigen, inwiefern die Auffassung der Vorinstanz geradezu willkürlich sein soll.
In den beiden Parteigutachten wird zwar naturgemäss eine andere Meinung vertreten als durch Prof. K._ und das Obergericht, doch ist insbesondere das breiter angelegte Gutachten M._ relativ zurückhaltend verfasst und anerkennt, dass im angesprochenen Problembereich gewisse Fragen unklar sind bzw. Raum lassen für verschiedene Auffassungen. Das Gutachten N._ hingegen geht einzig auf Teilfragen unter der Hypothese der Anwendbarkeit des griechischen internationalen Privatrechts ein. Mit beiden Gutachten wird somit nicht im Sinne von Art. 106 Abs. 2 BGG dargetan, inwiefern die Schlussfolgerungen der Vorinstanz willkürlich, d.h. offensichtlich unhaltbar oder einen unumstrittenen Rechtsgrundsatz krass verletzend (<ref-ruling> E. 4.1 S. 133), sein sollen. Folglich ist auf die Rüge der fehlerhaften Feststellung des anwendbaren Rechts nicht einzutreten.
5. Die Beschwerdeführer wiederholen schliesslich ihre Ausführungen aus der Arresteinsprache zum Bestand von Forderungen gegen die Beschwerdegegnerin. Sie bringen zwar vor, es treffe entgegen den obergerichtlichen Ausführungen nicht zu, dass im Arresteinspracheverfahren keine Gegenforderungen geltend gemacht werden könnten. Abgesehen davon, dass das Obergericht einen Vorbehalt zugunsten eines liquiden Urkundenbeweises angebracht hat, begründen sie ihre Auffassung nicht weiter, womit auf diese Rüge nicht einzutreten ist.
6. Die Beschwerde ist folglich abzuweisen, soweit auf sie eingetreten werden kann. Bei diesem Ausgang des Verfahrens tragen die Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu gleichen Teilen und unter solidarischer Haftung für den Gesamtbetrag (Art. 66 Abs. 1 i.V.m. Abs. 5 BGG). Mangels Einholung einer Vernehmlassung wird auf die Zusprechung einer Parteientschädigung verzichtet.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 13'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, Appellationshof, 2. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 29. Dezember 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Zingg