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.