Sachverhalt:
A. X._ und Y._ (Arrestschuldner) erhoben am 31. Januar 2011 Arresteinsprache gegen einen auf Begehren der Z._ SA (Arrestgläubigerin) ausgestellten Arrestbefehl. Das Regionalgericht Oberland wies die Einsprache am 21. März 2011 ab. Der Entscheid wurde dem Rechtsvertreter der Arrestschuldner am 24. März 2011 zugestellt.
B. Gegen diesen Entscheid erhoben die Arrestschuldner mit E-Mail ihres Rechtsvertreters vom 4. April 2011 Beschwerde an das Obergericht des Kantons Bern. Mit Entscheid vom 7. September 2011 trat das Obergericht auf die Beschwerde nicht ein.
C. Dagegen erhoben die Arrestschuldner (fortan: Beschwerdeführer) am 21. September 2011 Beschwerde in Zivilsachen. Sie verlangen die Aufhebung des angefochtenen Entscheids und Rückweisung an das Obergericht zur materiellen Beurteilung.
Die Z._ SA (fortan: Beschwerdegegnerin) hat auf Vernehmlassung verzichtet, allerdings Anträge im Kostenpunkt gestellt. Das Obergericht beantragt Abweisung der Beschwerde, soweit auf sie einzutreten sei.

Erwägungen:
1. Die rechtzeitig erhobene Beschwerde (<ref-law>) richtet sich gegen den Entscheid eines oberen Gerichts, das kantonal letztinstanzlich auf Rechtsmittel hin geurteilt hat (<ref-law>). Der Entscheid betrifft eine Schuldbetreibungssache (<ref-law>) und der erforderliche Streitwert ist erreicht (<ref-law>). Die Streitsache unterliegt demnach der Beschwerde in Zivilsachen (<ref-law>).
Der Beschwerdeentscheid gemäss <ref-law> ist ein Endentscheid nach <ref-law> (Urteil 5A_614/2011 vom 28. November 2011 E. 1; vgl. auch <ref-ruling> E. 1 S. 590). Er beschlägt ausschliesslich das jeweilige 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 Sinne von <ref-law> (<ref-ruling> E. 1.2 S. 234). Damit kann einzig die Verletzung verfassungsmässiger Rechte gerügt werden. Verfassungsrügen müssen in der Beschwerde präzise vorgebracht und begründet werden (<ref-law>; <ref-ruling> E. 1.4 S. 400 f.; <ref-ruling> E. 1.4.2 S. 254 mit Hinweisen). Dies bedeutet, dass anhand der Erwägungen des angefochtenen Entscheids klar und detailliert darzulegen ist, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-ruling> E. 1.2 S. 234 mit Hinweisen).
2. Das Obergericht hat festgehalten, der Anwalt der Beschwerdeführer habe seine Beschwerde an die gewöhnliche E-Mail-Adresse des Obergerichts versandt. Die Eingabe sei elektronisch signiert gewesen und soweit ersichtlich am 4. April 2011 um 23.43 Uhr beim Obergericht eingetroffen. Der 4. April 2011 sei zugleich der letzte Tag der Beschwerdefrist gewesen. Auf Aufforderung hin habe der Anwalt die Beschwerde am 20. April 2011 in Papierform nachgereicht.
Das Obergericht hat sodann erwogen, elektronische Eingaben an eine Behörde müssten an die Adresse der von ihr verwendeten anerkannten Zustellplattform gesendet werden (Art. 4 der Verordnung vom 18. Juni 2010 über die elektronische Übermittlung im Rahmen von Zivil- und Strafprozessen sowie von Schuldbetreibungs- und Konkursverfahren; SR 272.1; nachfolgend: VeÜ-ZSSchKG). Nach Art. 5 VeÜ-ZSSchKG veröffentliche die Bundeskanzlei im Internet ein Verzeichnis mit Behördenadressen. Dieses führe die Adresse der jeweiligen Behörde für die elektronische Eingabe auf. Der Kanton Bern habe zum Zeitpunkt der Beschwerde wie auch des obergerichtlichen Urteils über keine funktionierende Umgebung für den Empfang von elektronischen und verschlüsselten Eingaben verfügt. Die bernischen Anwälte seien über die fehlende Möglichkeit zur elektronischen Übermittlung informiert worden. Insbesondere sei dem betreffenden Anwalt die Tatsache bekannt gewesen, dass die elektronische Übermittlung aus technischen Gründen nicht möglich sei. Im Kanton Bern existiere somit keine Zustellplattform im Sinne von Art. 2 und Art. 4 VeÜ-ZSSchKG und das Obergericht habe keine Adresse für elektronische Eingaben im Sinne von Art. 5 Abs. 2 lit. b VeÜ-ZSSchKG. Demgemäss habe die Bundeskanzlei auch keine Adresse veröffentlicht. Rechtssuchende könnten sich nicht mit einer elektronischen Eingabe an eine nicht den Vorgaben der VeÜ-ZSSchKG entsprechende E-Mail-Adresse über die dem betreffenden Anwalt bekannte Tatsache hinwegsetzen, dass die elektronische Übermittlung aus technischen Gründen derzeit nicht möglich sei. Die Eingabe sei zwar elektronisch signiert (Art. 7 VeÜ-ZSSchKG), erfülle aber die Voraussetzungen für eine gültige elektronische Übermittlung nicht. In der Rechtsmittelbelehrung des angefochtenen erstinstanzlichen Entscheids sei im Übrigen festgehalten, dass Eingaben per E-Mail nicht rechtsgültig seien, dass sie keine fristwahrende Wirkung hätten und dass elektronische Eingaben nur unter bestimmten Voraussetzungen erfolgen könnten. Die Papierexemplare der Beschwerde seien der Post erst nach Ablauf der Beschwerdefrist überreicht worden. Auf die Beschwerde sei deshalb nicht einzutreten.
Das Obergericht hat in seiner Vernehmlassung an das Bundesgericht ausgeführt, es sei ihm inzwischen möglich, elektronische Eingaben entgegenzunehmen.
3. Die Beschwerdeführer machen geltend, das Beharren auf Zustellung über eine anerkannte Zustellplattform sei überspitzt formalistisch und verletze den Anspruch auf rechtliches Gehör. Zudem sei das Willkürverbot verletzt, wenn auf der Zustellung via anerkannte Zustellplattform beharrt werde, obschon eine solche bundesrechtswidrig nicht zur Verfügung stehe. Im Einzelnen führen sie aus, in der Rechtsmittelbelehrung des erstinstanzlichen Urteils stehe der Standardsatz, wonach unter bestimmten Voraussetzungen Eingaben elektronisch erfolgen könnten. Der Kanton Bern publiziere zudem auf der Website seiner Justizbehörden und auf der Website der Bundeskanzlei, es bestehe ein elektronischer Zugang zum Gericht. Der Rechtssuchende dürfe sich deshalb darauf verlassen, dass elektronische Eingaben tatsächlich möglich seien. Wenn eine Zustellplattform noch nicht verfügbar sei, müssten Beschwerden an eine E-Mail-Adresse des angerufenen Gerichts gesandt werden können. Der Eingang lasse sich mit den bestehenden technischen Möglichkeiten auch so nachweisen. Die elektronische Übermittlung über eine anerkannte Plattform diene der Fixierung des Eingangs der E-Mail bei der angerufenen Behörde und der Sicherstellung der Verwendung einer einheitlichen E-Mail-Adresse. Diesem Zweck sei durch den Versand der digital signierten Dokumente an die vom Gericht selber verwendete E-Mail-Adresse Genüge getan worden. Der Kanton Bern habe sich als einziger Kanton nicht den bestehenden Zustellplattformen (IncaMail und Privasphere) angeschlossen, sondern erarbeite eine eigene Lösung. Er hätte ohne weiteres in der Zwischenzeit einen Anschluss bei einem dieser Anbieter einrichten können. Die fehlende Möglichkeit zur Entgegennahme elektronischer Eingaben sei deshalb nicht auf technische, sondern auf finanzielle Gründe zurückzuführen. Der Anwalt der Beschwerdeführer habe schliesslich zahlreiche Eingaben an Gerichte im Kanton Bern per E-Mail übermittelt und Fristversäumnis sei nie gerügt worden.
4. Die Beschwerde ist unbegründet, soweit auf sie eingetreten werden kann. Zwar ist nicht ohne weiteres nachvollziehbar, wieso der Kanton Bern die Voraussetzungen zum Empfang elektronischer Eingaben im April 2011 noch nicht bereitstellen konnte (vgl. <ref-law>). Jedoch können die Beschwerdeführer unter den gegebenen Umständen daraus nicht ableiten, die Vorinstanz verfalle in überspitzten Formalismus oder verletze das Willkürverbot, wenn sie auf elektronische Eingaben nicht eintritt, welche die gesetzlichen Voraussetzungen an die Form solcher Eingaben nicht erfüllen. Die Vorinstanz hat auf die einschlägigen Normen der VeÜ-ZSSchKG hingewiesen, die die Form der elektronischen Zustellung regeln. So sieht Art. 4 VeÜ-ZSSchKG die Zustellung über eine anerkannte Zustellplattform vor und Art. 2 VeÜ-ZSSchKG listet die Anforderungen an solche Zustellplattformen auf. Eine Eingabe auf dem Wege einer gewöhnlichen E-Mail mit elektronisch signierten Anhängen, wie sie die Beschwerdeführer vorgenommen haben, ist dort nicht vorgesehen. Die Beschwerdeführer behaupten, die von ihnen gewählte Lösung sei technisch gleichwertig mit der Zustellung über eine anerkannte Plattform. Sie belegen dies jedoch nicht näher. Bereits der Blick auf Art. 2 VeÜ-ZSSchKG lässt an der behaupteten Gleichwertigkeit zweifeln. Mit der VeÜ-ZSSchKG und den von ihr verfolgten Zwecken setzen sich die Beschwerdeführer nicht auseinander. Welchen Eindruck der Kanton gegenüber Rechtssuchenden hinsichtlich der Möglichkeit zu elektronischen Eingaben vermittelt hat (z.B. durch seinen Internetauftritt), spielt vorliegend keine Rolle. Die diesbezüglichen Ausführungen gehen an den massgeblichen Erwägungen der Vorinstanz vorbei, die auf die Kenntnisse der bernischen Anwaltschaft und des vorliegend betroffenen Rechtsvertreters abstellen. Der Anwalt der Beschwerdeführer bestreitet die obergerichtliche Feststellung nicht, dass er um das Fehlen einer Zustellplattform im Kanton Bern und die fehlende Möglichkeit zu elektronischen Eingaben wusste. Er bestreitet auch nicht, dass die erstinstanzliche Rechtsmittelbelehrung ausdrücklich festhielt, Eingaben per E-Mail seien nicht rechtsgültig und hätten keine fristwahrende Wirkung. Dass andere Gerichte des Kantons Bern Eingaben per E-Mail akzeptiert hätten, ist demgegenüber eine unbelegte Behauptung, aus welcher die Beschwerdeführer selbst bei ihrer Richtigkeit nichts zu ihren Gunsten ableiten könnten. Aufgrund seiner Kenntnisse durfte der Rechtsvertreter nicht darauf vertrauen, dass das Obergericht seine Eingabe per E-Mail als zulässig erachten würde. Im Beharren des Obergerichts auf der vom Gesetz vorgesehenen Form einer Eingabe kann folglich weder überspitzter Formalismus noch Willkür gesehen werden, soweit die Verletzungen der entsprechenden verfassungsmässigen Verbote überhaupt genügend begründet werden. Da es den Beschwerdeführern offengestanden wäre, sich innerhalb der Beschwerdefrist in Papierform an das Obergericht zu wenden, kann auch von einer Verletzung des rechtlichen Gehörs (oder eher einer Verletzung des Verbots der Rechtsverweigerung) nicht die Rede sein.
5. Bei diesem Ausgang des Verfahrens tragen die Beschwerdeführer die Gerichtskosten (<ref-law>). Die Beschwerdegegnerin verlangt für diesen Verfahrensausgang zwar eine Parteientschädigung. Da sie aber auf eine Vernehmlassung in der Sache verzichtet hat, ist ihr keine Entschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von insgesamt Fr. 1'500.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Es wird keine Parteientschädigung gesprochen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, Zivilabteilung, 1. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 27. Januar 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Zingg