Sachverhalt:
A. Die Anwaltskommission des Kantons Obwalden führte gegen Rechtsanwalt und Notar X._ eine Disziplinaruntersuchung. Nach Abschluss des Verfahrens stellte die Anwaltskommission ihren Disziplinarentscheid vom 25. August 2009 vor Eintritt der Rechtskraft der Notariatskommission des Kantons Obwalden zu, bei welcher ebenfalls ein Verfahren gegen X._ hängig war. Im Disziplinarentscheid wurden ferner Handlungen von Rechtsanwalt Y._, einem Büropartner von X._, erwähnt.
Am 22. Februar 2010 reichten X._ und Y._ beim Obergericht des Kantons Obwalden gegen die Mitglieder der Anwaltskommission Strafanzeige wegen des Verdachts der Amtsgeheimnisverletzung im Sinne von <ref-law> ein. Das Obergericht leitete die Strafanzeige am 10. März 2010 zuständigkeitshalber an das Verhöramt Obwalden weiter. Mit Schreiben vorn 15. März 2010 beantragte das Verhöramt dem Obergericht, für die Strafuntersuchung sei ein ausserordentlicher Verhörrichter zu ernennen.
Am 12. April 2010 wurde Rechtsanwältin Z._ als ausserordentliche Verhörrichter-Stellvertreterin bestellt und mit lnkrafttreten der Justizreform als ausserordentliche Staatsanwalt-Stellvertreterin eingesetzt. Am 27. Dezember 2010 reichten X._ und Y._ beim Obergericht eine Rechtsverzögerungsbeschwerde ein, in welcher sie Z._ Untätigkeit vorwarfen.
Am 21. Januar 2011 teilte Z._ X._ und Y._ mit, dass sie beabsichtige, das Strafverfahren gegen die Mitglieder der Anwaltskommission einzustellen.
Nachdem das Rechtsverzögerungsverfahren vor Obergericht vom 27. Januar bis 24. August 2011 sistiert worden war, entschied das Obergericht am 8. November 2011 was folgt:
"1. Die Beschwerde wird abgewiesen.
2. Es wird festgestellt, dass die Beschwerdeführer im Sinne der Erwägungen in der Beschwerde vom 27. Dezember 2010 den durch die gute Sitte gebotenen Anstand verletzt haben.
3. Die Beschwerdeführer Dr. X._ und lic.iur. Y._ werden deswegen im Sinne der Erwägungen mit je einer Ordnungsbusse von Fr. 300.-- bestraft.
4. Die Beschwerdeführer haben die Kosten des Beschwerdeverfahrens von Fr. 1'878.70 (Fr. 1'500.-- Gerichtsgebühr, Fr. 130.-- Schreibgebühren sowie Fr. 248.70 Kanzleikosten) zu tragen."
B. Gegen diesen Entscheid führen X._ und Y._ am 9. Dezember 2011 Beschwerde in Strafsachen ans Bundesgericht mit den folgenden Anträgen:
"1. Die Beschwerde sei gutzuheissen und demzufolge seien die Ziffern 1 und 4 des Urteils des Obergerichts des Kantons Obwalden vom 8. November 2011 (B 10/028/rh) aufzuheben.
2. Es sei festzustellen, dass die a. o. Staatsanwalt-Stellvertreterin, lic. iur. Z._, das Strafverfahren AK-Nr. 010 10 379/BSC ohne sachliche Notwendigkeit und damit in Verletzung des verfassungsmässigen Anspruchs auf Beurteilung innert angemessener Frist (<ref-law>) über Gebühr hinausgezögert bzw. nicht anhand genommen hat.
3. Die a. o. Staatsanwalt-Stellvertreterin, lic. iur. Z._ sei anzuweisen, die Strafuntersuchung AK-Nr. 010 10 379/BSC betreffend Amtsgeheimnisverletzung nunmehr ohne weiteren Verzug fortzusetzen und innert nützlicher Frist abzuschliessen.
4. Es sei festzustellen, dass das Obergericht des Kantons Obwalden den Anspruch der Beschwerdeführer auf rechtliches Gehör mangels hinreichender Begründung des angefochtenen Urteils vom 8. November 2011 (B 10/028/rh) verletzt habe.
5. Eventualiter sei die Sache an die Vorinstanz zurückzuweisen
6. AIles unter Kosten- und Entschädigungsfolgen zulasten des Kantons Obwalden."
Z._ und das Obergericht beantragen in ihren Vernehmlassungen vom 5. respektive 10. Januar 2012 die Beschwerdeabweisung. In ihrer Stellungnahme vom 19. Januar 2012 halten die Beschwerdeführer an ihrem Standpunkt fest. Diese Eingabe wurde Z._ und dem Obergericht zur Kenntnisnahme zugestellt.

Erwägungen:
1. Gemäss <ref-law> beurteilt das Bundesgericht Beschwerden gegen Entscheide in Strafsachen. Der angefochtene Entscheid ist kantonal letztinstanzlich (<ref-law>). Er schliesst das Strafverfahren nicht ab (Art. 90 f. BGG). Es liegt ein Zwischenentscheid im Sinne von <ref-law> vor, welcher nur dann der Beschwerde ans Bundesgericht unterliegt, wenn er einen nicht wieder gutzumachenden Nachteil bewirken kann (Abs. 1 lit. a) oder wenn die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (Abs. 1 lit. b). Vorliegend kommt nur die erste Variante (Abs. 1 lit. a) in Betracht. In der Beschwerdeschrift ist konkret darzulegen, inwiefern die Voraussetzung des nicht wieder gutzumachenden Nachteils erfüllt ist, soweit dies nicht offensichtlich ist.
Indessen wird nach der bundesgerichtlichen Rechtsprechung ausnahmsweise auf die Voraussetzung des nicht wieder gutzumachenden Rechtsnachteils verzichtet, wenn ein Beschwerdeführer die Rüge der formellen Rechtsverweigerung in der Form der Rechtsverzögerung erhebt (vgl. Urteil 1B_388/2011 vom 5. September 2011 E. 1.3). Die Beschwerdeführer rügen, die bisherige Dauer des Strafverfahrens sei zu lang. Auf ihre Beschwerde ist einzutreten.
2. 2.1 Die Beschwerdeführer fechten den vorinstanzlichen Entscheid nicht an, soweit darin festgestellt wurde, sie hätten in ihrer Beschwerde vom 27. Dezember 2010 an die Vorinstanz den durch die guten Sitten gebotenen Anstand verletzt, und soweit sie deswegen mit einer Ordnungsbusse von je Fr. 300.-- bestraft wurden (Dispositiv-Ziffern 2 und 3 des vorinstanzlichen Entscheids). Hingegen rügen sie, die Vorinstanz habe ihre Rechtsverzögerungsbeschwerde zu Unrecht abgewiesen.
2.2 Die Vorinstanz geht insoweit von folgendem Sachverhalt aus: Am 12. April 2010 wurde Z._ als ausserordentliche Staatsanwalt-Stellvertreterin eingesetzt. Die Beschwerdeführer erkundigten sich mehrmals telefonisch und per E-Mail bei ihr nach dem Stand der Strafuntersuchung. Anfangs Juni 2010 stellten sie ein Akteneinsichtsgesuch, welchem am 22. September 2010 entsprochen wurde. Mit Eingabe vom 24. September 2010 unterbreiteten sie Z._ verschiedene Fragen, die diese am 30. September 2010 beantwortete. Am 20. Oktober 2010 stellte Z._ den Beschwerdeführern weitere Akten zu. Am 27. Dezember 2010 erhoben die Beschwerdeführer Rechtsverzögerungsbeschwerde.
2.3 Die Beschwerdeführer führen in ihrer Beschwerde ans Bundesgericht aus, sie hätten sich mehrmals bei Z._ nach dem Stand der Strafuntersuchung erkundigt und die unverzügliche Bearbeitung verlangt. Z._ sei jedoch ohne nachvollziehbare Gründe untätig geblieben und habe bis zur Einreichung der Rechtsverzögerungsbeschwerde am 27. Dezember 2010 keinerlei Untersuchungshandlungen vorgenommen und auch keine solchen in Aussicht gestellt. Das Strafverfahren gegen die Anwaltskommission wegen Amtsgeheimnisverletzung sei weder in tatsächlicher noch in rechtlicher Hinsicht komplex. Vielmehr sei der Sachverhalt gut überblickbar und dokumentiert und die zu beurteilende Rechtsfrage klar. Den Fall während knapp neun Monaten liegen zu lassen, missachte den in <ref-law> verankerten Anspruch auf Beurteilung innert angemessener Frist.
Des Weiteren habe die Vorinstanz den Sachverhalt willkürlich festgestellt und sich im angefochtenen Entscheid in Verletzung der Begründungspflicht gemäss <ref-law> nicht hinreichend mit den in der Beschwerde erhobenen Rügen auseinandergesetzt.
2.4 Die Vorinstanz hat erwogen, die Strafuntersuchung sei, was den Sachverhalt und den zu beurteilenden Tatbestand betreffe, nicht einfach. Die Beschwerdeführer sähen in der Tatsache, dass die Anwaltskommission ihren Disziplinarentscheid gegen den Beschwerdeführer 1 vor Eintritt der Rechtskraft der Notariatskommission zugestellt habe, eine Verletzung des Amtsgeheimnisses. Bei der Beurteilung, ob das Vorgehen der Anwaltskommission rechtens gewesen sei, stellten sich insbesondere datenschutz- und aufsichtsrechtliche Fragen, welche "recht komplex" seien. Bei objektiver Betrachtung sei eine Verfahrensdauer von knapp neun Monaten bis zur Einreichung der Rechtsverzögerungsbeschwerde nicht unangemessen lang. Allerdings sei nunmehr eine zügige Weiterführung der Strafuntersuchung im Interesse der beschuldigten Mitglieder der Anwaltskommission und der Beschwerdeführer angezeigt.
2.5 Z._ hält in ihrer Stellungnahme vom 5. Januar 2012 fest, Beweiserhebungen, so auch Einvernahmen mit beschuldigten Personen, seien einzig vorzunehmen, soweit diese zur Abklärung des relevanten Sachverhalts mit Blick auf den eingeklagten Tatbestand notwendig seien. Im zu beurteilenden Fall sei der relevante Sachverhalt aktenkundig und nicht bestritten, weshalb sie keine Untersuchungshandlungen angeordnet und durchgeführt habe. Im Übrigen hätten die Beschwerdeführer auch keinerlei Beweisanträge gestellt. Im Herbst 2010 sei sie mit der Redaktion des Einstellungsentscheids befasst gewesen, zumal sie bereits den objektiven Tatbestand der Amtsgeheimnisverletzung als nicht gegeben erachtet habe. Sie bestreite, dass die gerügte Verfahrensdauer unangemessen lang im Sinne der Rechtsprechung sei.
2.6 Die Strafbehörden nehmen die Strafverfahren unverzüglich an die Hand und bringen sie ohne unbegründete Verzögerung zum Abschluss (<ref-law>; SR 312.0). Diese Konkretisierung des in <ref-law> verankerten Grundsatzes auf Beurteilung innert angemessener Frist ist für die Behörden der Strafverfolgung (Art. 12 und 15 ff. StPO) und die Gerichte (Art. 13 und 18 ff. StPO) gleichermassen verbindlich.
Nach der bundesgerichtlichen Rechtsprechung wird der Anspruch auf Beurteilung innert angemessener Frist missachtet, wenn eine Sache über Gebühr verschleppt wird. Die Beurteilung der angemessenen Verfahrensdauer entzieht sich starren Regeln. Es ist vielmehr in jedem Einzelfall zu prüfen, ob sich die Dauer unter den konkreten Umständen als angemessen erweist. Der Streitgegenstand und die damit verbundene Interessenlage können raschere Entscheide erfordern oder längere Behandlungsperioden erlauben. Entscheidend ist weiter der Umfang und die Komplexität der aufgeworfenen Sachverhalts- und Rechtsfragen. Kriterien für die Angemessenheit der Verfahrensdauer im Rahmen von Strafverfahren bilden etwa die Schwere des Tatvorwurfs, die Komplexität des Sachverhalts, die dadurch gebotenen Untersuchungshandlungen, das Verhalten der beschuldigten Person und dasjenige der Behörden (z.B. unnötige Massnahmen oder Liegenlassen des Falls) sowie die Zumutbarkeit für die beschuldigte Person. Strafverfahren sind zügig voranzutreiben, um die beschuldigte Person nicht unnötig über die gegen sie erhobenen Vorwürfe im Ungewissen zu lassen (zum Ganzen: <ref-ruling> E. 2.3 und 3.1 S. 272 f.; Urteil 1B_388/2011 vom 5. September 2011 E. 2.2). Anspruch auf Verfahrensbeschleunigung haben primär beschuldigte Personen, in etwas geringerem Mass jedoch auch die übrigen Verfahrensbeteiligten wie die Privatklägerschaft (vgl. Botschaft vom 21. Dezember 2005 zur Vereinheitlichung des Strafprozessrechts, BBl 2006 1130 Ziff. 2.1.2; Niklaus Schmid, Schweizerische Strafprozessordnung, Praxiskommentar, 2009, N. 1 zu <ref-law>).
2.7 Im Strafverfahren gegen die Mitglieder der Anwaltskommission ist zu klären, ob diese durch Übermittlung ihres Disziplinarentscheids gegen den Beschwerdeführer 1 an die Notariatskommission vor Eintritt der Rechtskraft des Entscheids den Tatbestand der Amtsgeheimnisverletzung erfüllt haben. Der massgebliche Sachverhalt ist unbestritten, für die rechtliche Beurteilung nicht entscheidend sind insbesondere die Hintergründe der gegen den Beschwerdeführer 1 geführten Disziplinaruntersuchung. Nach Auffassung der ausserordentlichen Staatsanwalt-Stellvertreterin Z._ erübrigen sich daher Einvernahmen oder andere Untersuchungshandlungen. In rechtlicher Hinsicht steht nur ein Tatbestand zur Diskussion und zu entscheiden ist eine klar umschriebene Rechtsfrage.
Zum Zeitpunkt der Einsetzung von Z._ als ausserordentliche Staatsanwalt-Stellvertreterin am 12. April 2010 war der massgebliche Sachverhalt erstellt und die Rechtsfrage bekannt. Z._ hat die Strafuntersuchung bis zum Einreichen der Rechtsverzögerungsbeschwerde durch die Beschwerdeführer am 27. Dezember 2010 nicht vorangetrieben, sondern sich nach eigenen Angaben aufs Aktenstudium und die Redaktion des Entscheids konzentriert. Erst im Januar 2011 stellte Z._ schliesslich in Aussicht, das Verfahren ohne Vornahme von Untersuchungshandlungen einstellen zu wollen. In diesem weder in tatsächlicher noch in rechtlicher Hinsicht komplexen Fall während knapp neun Monaten (gegen aussen hin) untätig zu bleiben, ist mit <ref-law> nicht vereinbar. Die Rüge der Verletzung des Rechtsverzögerungsverbots erweist sich damit als begründet.
3. Die Beschwerde ist gutzuheissen, und die Ziffern 1 und 4 des Entscheids des Obergerichts vom 8. November 2011 sind aufzuheben. Die ausserordentliche Staatsanwalt-Stellvertreterin Z._ ist anzuweisen, die Strafuntersuchung AK-Nr. 010 10 379/BSC betreffend Amtsgeheimnisverletzung unverzüglich fortzusetzen und umgehend abzuschliessen. Mit dieser Anweisung erübrigt sich die von den Beschwerdeführern beantragte förmliche Feststellung der Rechtsverzögerung im Dispositiv des bundesgerichtlichen Urteils. Ebenso erübrigt sich ein Eingehen auf die von den Beschwerdeführern erhobenen Rügen der Verletzung des Willkürverbots gemäss <ref-law> und der Begründungspflicht nach <ref-law>.
Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Die Beschwerdeführer treten als Anwälte in eigener Sache auf. Die Komplexität der Angelegenheit und der gerechtfertigte Arbeitsaufwand übersteigen dabei nicht den Rahmen dessen, was dem Einzelnen zur Besorgung seiner persönlichen Angelegenheiten zugemutet werden kann. Den obsiegenden Beschwerdeführern ist deshalb keine Parteientschädigung zuzusprechen (vgl. Urteil 1C_436/2009 E. 5.3; <ref-ruling> E. 5 S. 304; 129 V 113 E. 4.1 S. 116; <ref-ruling> E. 5b S. 519 f.; je mit Hinweisen).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, und die Ziffern 1 und 4 des Entscheids des Obergerichts des Kantons Obwalden vom 8. November 2011 werden aufgehoben. Die ausserordentliche Staatsanwalt-Stellvertreterin Z._ wird angewiesen, die Strafuntersuchung AK-Nr. 010 10 379/BSC betreffend Amtsgeheimnisverletzung unverzüglich fortzusetzen und umgehend abzuschliessen.
2. Es werden keine Gerichtskosten erhoben und keine Parteientschädigungen zugesprochen.
3. Dieses Urteil wird den Beschwerdeführern, der ausserordentlichen Staatsanwalt-Stellvertreterin Z._ und dem Obergericht des Kantons Obwalden schriftlich mitgeteilt.
Lausanne, 20. Februar 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Stohner