Sachverhalt:
A. Am 23. Juni 2002 schloss Z._, wohnhaft in Monaco, mit dem "Comité International pour le Français langue européenne" (nachfolgend: Comité International), handelnd durch dessen Präsidenten W._, eine Vereinbarung ab, wonach Z._ sich unwiderruflich verpflichtete, dem Comité International bis zum 22. Dezember 2003 Fr. 2'500'000.-- zu überweisen oder im Fall des Todes durch ihre Erben überweisen zu lassen.
Am 3. April 2003 verfasste Z._ eigenhändig ein erstes Testament, nach dessen Wortlaut sie ihrem Adoptivsohn Y._ eine jährliche Rente auf Lebenszeit von Fr. 50'000.-- vermachte. In einem zweiten und dritten Testament, beide datiert vom 18. Juni 2003, vermachte sie Y._ eine monatliche Rente von Fr. 25'000.--. Schliesslich annullierte Z._ in einem vierten Testament vom 2. Juli 2003 die vorangehenden Verfügungen, setzte W._ als Testamentsvollstrecker ein, vermachte Y._ die zwei Appartements in Monaco, W._ drei Schmuckstücke sowie dem Comité International zusätzlich zu ihrem Versprechen vom 23. Juni 2002 über Fr. 2'500'000.-- weitere Fr. 3'000'000.--. Der Saldo sollte an Y._ gehen. Z._ verstarb am 9. Juli 2003 in Monaco. Das Testament vom 2. Juli 2003 wurde in der Folge angefochten. Mit Urteil vom 17. November 2006 bestätigte das Berufungsgericht des Fürstentums Monaco dessen Gültigkeit.
Gemäss der von V._, Notar in Monaco, erstellten und von Y._ mitunterzeichneten Urkunde vom 7. Oktober 2003 mit dem Titel "Notoriété après le décès de Madame Z._" ("Erbenschein") hinterliess die Erblasserin Z._ als Universalerben ihren Adoptivsohn Y._. Dieser sei erbfähig bis zu 75 % des gesamten beweglichen Nachlasses und der Immobilien in der Schweiz sowie zu 50 % des monegassischen Nachlasses. Zugleich wurde Y._ zur Auflage gemacht, die testamentarischen Verfügungen der Erblasserin auszuführen, wenn nötig herabgesetzt auf die verfügbare Quote. Weiter wurde in der Urkunde darauf hingewiesen, dass nach dem in Monaco anwendbaren Internationalen Privatrecht und dem Personalstatut für das Mobiliar das schweizerische Recht und für die Immobilien das Recht am Ort der gelegenen Sache gelte.
V._ hatte zum Zeitpunkt der Erstellung des "Erbenscheins" vom 7. Oktober 2003 keine Kenntnis vom vierten Testament von Z._ vom 2. Juli 2003. Dieses Testament war bei einem Geistlichen in Rom deponiert und wurde W._ am 26. Oktober 2003 ausgehändigt. Dieser hinterlegte das Testament bei V._ und liess dem Rechtsvertreter von Y._, Rechtsanwalt X._, mit Schreiben vom 29. Oktober 2003 eine Kopie des Testaments zukommen. Am 10. November 2003 sandte V._ das Testament vom 2. Juli 2003 X._ (nochmals) zu. Dieser bestätigte den Empfang mit E-Mail vom 13. November 2003.
In einer Urkunde vom 22. Januar 2004 präzisierte V._ unter Bezugnahme auf das Testament vom 2. Juli 2003, die Erblasserin Z._ habe W._ als Testamentsvollstrecker eingesetzt. Diese Urkunde wurde X._ am 17. Februar 2004 ausgehändigt.
B. Am 11. November 2003 erteilte Y._ unter Vorlage des "Erbenscheins" vom 7. Oktober 2003 der UBS AG in Zürich den Auftrag, die Bankbeziehungen seiner Mutter bei der UBS AG in Zürich aufzulösen und den Saldo auf sein Konto bei der UBS AG in Rapperswil zu überweisen.
Am 18. März 2004 ersuchte X._ im Namen und Auftrag von Y._ unter Vorlage des "Erbenscheins" vom 7. Oktober 2003 die Walliser Kantonalbank, die Konten der verstorbenen Z._ zu saldieren und den Saldo auf das Konto von Y._ bei der UBS AG in Rapperswil zu überweisen. Der Auftrag wurde am 30. März 2004 ausgeführt.
Mit Schreiben vom 24. März 2004 liess Y._ unter Vorlage des "Erbenscheins" vom 7. Oktober 2003 die Konten seiner Mutter bei der Zuger Kantonalbank saldieren und den Saldo auf sein Konto bei dieser Bank überweisen. Die Überweisung erfolgte am 29. März 2004.
C. Am 10. Januar 2006 reichte W._ beim damaligen Untersuchungsrichteramt des Kantons Wallis eine Strafanzeige gegen Y._ wegen Urkundenfälschung (<ref-law>) und Geldwäscherei (<ref-law>) ein. Am 9. März 2006 erstattete das Comité International Strafanzeige im Wesentlichen mit gleichem Inhalt. In den beiden Strafanzeigen wird Y._ bzw. dessen Rechtsvertreter insbesondere vorgeworfen, den Banken lediglich den "Erbenschein" vom 7. Oktober 2003, welcher das Testament vom 2. Juli 2003 unberücksichtigt lässt, vorgelegt und hierdurch die Saldierung der Konten der Erblasserin und die Überweisung der Gelder auf eigene Konten erwirkt zu haben.
Mit Entscheid vom 12. März 2009 gab der Untersuchungsrichter den beiden Strafanzeigen keine Folge. Eine dagegen erhobene Beschwerde hiess das Kantonsgericht des Kantons Wallis mit Entscheid vom 17. September 2009 gut und wies die Sache an den Untersuchungsrichter zurück.
Nach Abschluss des polizeilichen Ermittlungsverfahrens eröffnete der Untersuchungsrichter am 1. Februar 2010 gegen Y._ und dessen Rechtsvertreter X._ ein Strafverfahren wegen Betrugs (<ref-law>), Urkundenfälschung (<ref-law>) und Geldwäscherei (<ref-law>).
Am 2. Juli 2010 schloss Y._ mit W._ und dem Comité International eine Vereinbarung ab; am 8. November 2010 zogen diese ihre Strafanzeigen zurück.
Der zuständige Staatsanwalt teilte am 12. November 2010 dem Untersuchungsrichter nach Einsicht in die Akten mit, er widersetze sich einer Einstellung des Strafverfahrens nicht, machte aber geltend, die Verzeigten hätten durch ihr Verhalten das Verfahren veranlasst, weshalb ihnen die Untersuchungskosten aufzuerlegen seien.
Am 14. Dezember 2010 stellte der Untersuchungsrichter das Strafverfahren gegen Y._ und X._ ein und auferlegte diesen Verfahrenskosten von je Fr. 1'400.--.
D. Gegen diesen Kostenentscheid erhoben Y._ und X._ je Berufung ans Kantonsgericht des Kantons Wallis mit den Anträgen, die Verfahrenskosten seien auf die Staatskasse zu nehmen und ihnen sei eine angemessene Parteientschädigung zuzusprechen.
Mit Urteil vom 30. November 2011 wies das Kantonsgericht die Rechtsmittel ab und auferlegte Y._ und X._ Verfahrenskosten von je Fr. 400.--.
E. Y._ und X._ führen je Beschwerde in Strafsachen ans Bundesgericht, mit denen sie im Wesentlichen beantragen, das Urteil des Kantonsgerichts vom 30. November 2011 und die Einstellungsverfügung vom 14. Dezember 2010 seien aufzuheben.
Das Kantonsgericht und die Staatsanwaltschaft verzichten auf Stellungnahmen zu den Beschwerden.
F. Mit Eingabe vom 16. April 2012 ersucht die Aufsichtskommission über die Rechtsanwälte des Kantons Zug unter Berufung auf Art. 15 des Bundesgesetzes über die Freizügigkeit der Anwältinnen und Anwälte vom 23. Juni 2000 (Anwaltsgesetz, BGFA; SR 935.61) um Zustellung des bundesgerichtlichen Urteils.

Erwägungen:
1. 1.1 Das Bundesgericht vereinigt mehrere Verfahren, wenn diese in einem engen sachlichen Zusammenhang stehen, namentlich wenn sie sich gegen denselben Entscheid richten, und wenn sie die gleichen Parteien sowie ähnliche oder gleiche Rechtsfragen betreffen. Diese Voraussetzungen sind im vorliegenden Fall erfüllt. Es rechtfertigt sich daher, die beiden Beschwerden gestützt auf <ref-law> in sinngemässer Anwendung von <ref-law> (SR 273) zu vereinigen und in einem einzigen Entscheid zu beurteilen.
1.2 Angefochten ist ein Rechtsmittelentscheid über die Kosten- und Entschädigungsregelung einer Verfahrenseinstellung, mithin eines Entscheids, der das Strafverfahren gegen die Beschwerdeführer abschliesst. Es handelt sich dabei um einen Endentscheid einer letzten kantonalen Instanz in einer Strafsache, gegen den die Beschwerde in Strafsachen zulässig ist (Art. 78 Abs. 1, Art. 80 Abs. 1, Art. 90 BGG). Den Beschwerdeführern wurden Kosten überbunden, und es wurde ihnen eine Entschädigung verweigert, weshalb sie zur Beschwerdeführung befugt sind (vgl. <ref-law>). Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass, sodass auf die Beschwerden grundsätzlich einzutreten ist.
Nicht einzutreten ist auf die Beschwerden allerdings insoweit, als dass die Beschwerdeführer die Aufhebung der Einstellungsverfügung vom 14. Dezember 2010 beantragen. Unterinstanzliche Entscheide sind mit Beschwerde in Strafsachen nicht selbstständig anfechtbar. Sie werden mit Blick auf den Devolutiveffekt durch den Entscheid der letzten kantonalen Instanz ersetzt und gelten mit der dagegen gerichteten Beschwerde als mitangefochten (vgl. <ref-ruling> E. 1.4 S. 144).
1.3 Die Beschwerde ans Bundesgericht kann wegen Rechtsverletzungen im Sinne der Art. 95 und 96 BGG geführt werden. Die Feststellung des Sachverhalts durch die Vorinstanz kann gemäss <ref-law> nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Verletzung von schweizerischem Recht im Sinne von <ref-law> beruht. Die Rüge der offensichtlich unrichtigen, d.h. willkürlichen Feststellung des Sachverhalts prüft das Bundesgericht gemäss <ref-law> nur insoweit, als sie in der Beschwerde explizit vorgebracht und substanziiert begründet worden ist. In der Beschwerde muss im Einzelnen dargelegt werden, inwiefern der angefochtene Entscheid an einem qualifizierten und offensichtlichen Mangel leidet. Auf eine bloss appellatorische Kritik am angefochtenen Urteil tritt das Bundesgericht nicht ein (<ref-ruling> E. 2.8 S.494).
2. Es stellt sich vorab die Frage des anwendbaren Rechts. Die Einstellungsverfügung datiert vom 14. Dezember 2010. Sie erging mithin vor Inkrafttreten der Schweizerischen Strafprozessordnung (StPO; SR 312.0) am 1. Januar 2011. Anwendbar ist deshalb die bisherige Strafprozessordnung des Kantons Wallis vom 22. Februar 1962 (StPO/VS).
3.1 3.1.1 Die Vorinstanz hat erwogen, es handle sich um einen internationalen Sachverhalt und gemäss IPRG (SR 291) stelle sich die Rechtslage wie folgt dar:
Sterbe eine Person mit letztem Wohnsitz im Ausland, so unterstehe gemäss <ref-law> der Nachlass demjenigen Recht, auf welches das Kollisionsrecht des ausländischen Wohnsitzstaats verweise, was vorliegend - da die Erblasserin keine Rechtswahl getroffen habe - unbestrittenermassen das monegassische Recht sei. Gemäss <ref-law> bestimme das auf den Nachlass anwendbare Recht, was zum Nachlass gehöre, wer in welchem Umfang daran berechtigt sei, wer die Schulden des Nachlasses trage und welche Rechtsbehelfe und Massnahmen zulässig seien (sog. Erbstatut; vorwiegend materielle Fragen). Die Durchführung der einzelnen Massnahmen richte sich hingegen nach dem Recht am Ort der zuständigen Behörde, und diesem Recht unterstünden namentlich die sichernden Massnahmen und die Nachlassabwicklung mit Einschluss der Willensvollstreckung (<ref-law>; sog. Eröffnungsstatut; vorwiegend formelle Fragen). Gemäss <ref-law> sei somit grundsätzlich die Gesamtheit des Nachlasses ans Erbstatut anzuknüpfen (Abs. 1), die formelle Nachlassabwicklung mit Einschluss der Willensvollstreckung richte sich hingegen nach dem Eröffnungsstatut (Abs. 2). In der Doktrin werde überwiegend die Meinung vertreten, <ref-law> erfasse einzig die verfahrensrechtlichen, nicht aber die materiellen Aspekte der Willensvollstreckung, sodass insoweit eine Spaltung zwischen Erb- und Eröffnungsstatut bestehen könne. Folge man dieser Auffassung, würden im zu beurteilenden Fall die materiellen Aspekte der Willensvollstreckung nach monegassischem Recht beurteilt.
Allerdings sei anzumerken, dass die Beschwerdeführer den Hinweis des Notars im "Erbenschein" vom 7. Oktober 2003, wonach auf den beweglichen Nachlass von Z._ in der Schweiz schweizerisches Recht zur Anwendung gelange, nicht beanstandet hätten, was wiederum für die Anwendbarkeit schweizerischen Rechts spreche.
3.1.2 Die Vorinstanz hat weiter hervorgehoben, diese Kontroverse, ob sich die Beurteilung der Rechtsstellung des Willens- bzw. Testamentsvollstreckers vorliegend nach schweizerischem oder monegassischem Recht richte, sei bezüglich der hier zu entscheidenden Frage der Kostenauflage jedoch nicht unmittelbar entscheidrelevant.
Im konkreten Fall sei erstellt und unbestritten, dass die Beschwerdeführer bereits im November 2003 vom Testament vom 2. Juli 2003 und damit von der Einsetzung von W._ als Testamentsvollstrecker Kenntnis gehabt hätten. Zudem habe X._ die notarielle Urkunde vom 22. Januar 2004 am 17. Februar 2004 ausgehändigt bekommen. Diese für die Beurteilung der Erbberechtigung wesentlichen Unterlagen hätten die Beschwerdeführer wissentlich und willentlich den Kantonalbanken vorenthalten und so die sofortige Herausgabe der Vermögen erwirkt. Dies stelle einen Verstoss gegen den Grundsatz von Treu und Glauben (<ref-law>) dar. Bei vollständiger Dokumentation hätten die Banken zweifelsfrei die Legitimation der Beschwerdeführer näher abgeklärt, Rücksprache mit dem Willens- bzw. Testamentsvollstrecker genommen und mit der Auflösung der Konten bis zur Klärung der Sach- und Rechtslage zugewartet. Würde bei der Beurteilung des anwendbaren Rechts auf den "Erbenschein" vom 7. Oktober 2003 abgestellt, fände schweizerisches Recht Anwendung, womit dem Willensvollstrecker weitreichende Kompetenzen zustünden. Jedenfalls sei strittig, dass, wie die Beschwerdeführer geltend machen, monegassisches Recht anwendbar sei. Da die involvierten Banken bei Kenntnis dieser Ausgangslage die Gelder nicht (sofort) überwiesen hätten, hätten sich die Beschwerdeführer mit ihrem treuwidrigen Vorgehen einen unrechtmässigen Vorteil verschafft. Die Beschwerdeführer hätten zudem schuldhaft gehandelt, da sie sich aufgrund der konkreten Umstände und ihrer persönlichen Situation hätten gewahr sein müssen, dass das Ersuchen um Auflösung der Bankkonten der Erblasserin die Einleitung eines Strafverfahrens verursachen könnte. Die Eröffnung einer Strafuntersuchung sei auch objektiv angezeigt gewesen, da das von den Beschwerdeführern gewählte widerrechtliche Vorgehen den dringenden Verdacht begründet habe, sie wollten den Begünstigten die ihnen zustehenden Vermögenswerte entziehen. Die Kostenauflage an die Beschwerdeführer sei damit rechtens.
3.2 Die Beschwerdeführer rügen eine offensichtlich unrichtige Feststellung des Sachverhalts, eine willkürliche Rechtsanwendung und die Verletzung der Unschuldsvermutung.
Sie bringen vor, die kantonalen Instanzen hätten willkürlich festgestellt, dass sie in zivilrechtlich vorwerfbarer Weise eine geschriebene oder ungeschriebene Verhaltensnorm verletzt und dadurch die Einleitung des Strafverfahrens veranlasst oder dessen Durchführung erschwert hätten. Entgegen der Auffassung der Vorinstanz hätten sie nicht gegen Treu und Glauben verstossen. Selbst wenn dem aber so wäre, würde der angefochtene Entscheid Bundesrecht verletzen, denn eine Kostenauflage könne nicht mit dem Verweis auf den allgemeinen Rechtsgrundsatz von Treu und Glauben begründet werden, da dieser keine deliktsrechtliche Schutznorm darstelle.
Entgegen den Ausführungen im angefochtenen Urteil könne die Frage des anwendbaren Rechts nicht offen gelassen werden. Folge man der überwiegend in der Doktrin vertretenen Auffassung, unterliege die Nachlassregelung inklusive der Frage der Rechtsstellung des Testamentsvollstreckers monegassischem Recht. Die Befugnisse des Testamentsvollstreckers nach monegassischem Recht seien sehr viel enger gefasst als jene des Willensvollstreckers nach schweizerischem Recht. Insbesondere habe Ersterer keine Verfügungsbefugnis. Die Beschwerdeführer betonen, bei Geltung monegassischen Rechts seien sie somit als Universalerbe bzw. als dessen Rechtsvertreter ohne Weiteres befugt gewesen, bei den Banken die Saldierung der Konten der Erblasserin und die Überweisung der Gelder zu verlangen. Da sie nach monegassischem Recht keinerlei Regeln verletzt hätten, könne auch nicht gesagt werden, sie hätten das Strafverfahren durch ein zivilrechtlich vorwerfbares Verhalten veranlasst. Die Kostenauflage sei daher unhaltbar.
3.3 Gemäss <ref-law>/VS hat die beschuldigte Person bei einer Verfahrenseinstellung die Verfahrenskosten nur zu tragen, wenn sie durch einen Verstoss gegen die Rechtsordnung das Strafverfahren veranlasst oder erschwert hat.
Nach <ref-law> und Art. 6 Ziff. 2 EMRK gilt jede Person bis zur rechtskräftigen Verurteilung als unschuldig. Nach der Rechtsprechung verstösst es gegen Verfassung und Konvention, in der Begründung des Entscheids, mit dem ein Freispruch oder eine Verfahrenseinstellung erfolgt und der beschuldigten Person Kosten auferlegt werden, dieser direkt oder indirekt vorzuwerfen, sie habe sich strafbar gemacht bzw. es treffe sie ein strafrechtliches Verschulden. Dagegen ist es mit Verfassung und Konvention vereinbar, einer nicht verurteilten beschuldigten Person die Kosten zu überbinden, wenn sie in zivilrechtlich vorwerfbarer Weise - d.h. im Sinne einer analogen Anwendung der sich aus <ref-law> ergebenden Grundsätze - gegen eine geschriebene oder ungeschriebene Verhaltensnorm, die aus der gesamten schweizerischen Rechtsordnung stammen kann, klar verstossen und dadurch das Strafverfahren veranlasst oder dessen Durchführung erschwert hat. Als solche Verhaltensnormen gelten - entgegen der Auffassung der Beschwerdeführer - insbesondere auch das Verbot des Handelns wider Treu und Glauben (<ref-law>) sowie das Verbot des rechtsmissbräuchlichen Handelns (<ref-law>). Jeder Verstoss gegen eine derartige Verhaltensnorm wird grundsätzlich als widerrechtlich aufgefasst (<ref-ruling> E. 2c S. 169; vgl. auch Urteil 6B_998/2010 vom 31. August 2011 E. 5.2). Des Weiteren setzt die Kostenauflage zulasten der beschuldigten Person aufgrund verwerflich bewirkter Untersuchungseinleitung adäquate Kausalität zwischen deren Verhalten, der eingeleiteten Untersuchung und den erwachsenen und aufzuerlegenden Kosten voraus. In tatsächlicher Hinsicht darf sich die Kostenauflage nur auf unbestrittene oder bereits klar nachgewiesene Umstände stützen. Diese Grundsätze gelten auch für die Verweigerung einer Parteientschädigung (Urteil 1B_12/2012 vom 20. Februar 2012 E. 2 mit Hinweisen).
Wird eine Kostenauflage wegen Verletzung der Unschuldsvermutung angefochten, so prüft das Bundesgericht frei, ob der Kostenentscheid direkt oder indirekt den Vorwurf einer strafrechtlichen Schuld enthält. Nur unter dem Gesichtswinkel der Willkür untersucht es, ob die beschuldigte Person in zivilrechtlich vorwerfbarer Weise gegen eine geschriebene oder ungeschriebene Verhaltensnorm klar verstossen und durch ihr Benehmen das Strafverfahren veranlasst oder dessen Durchführung erschwert hat. Insoweit greift ausschliesslich <ref-law> Platz, wonach die kantonalen Kostenbestimmungen - vorliegend <ref-law>/VS - nicht willkürlich angewendet werden dürfen (Urteil 1B_497/2011 vom 30. November 2011 E. 2.4 mit Hinweis auf BGE 116 la 162 E. 2f S. 175 f.).
3.4 Die von den Beschwerdeführern erhobene Rüge der Verletzung der Unschuldsvermutung ist unbegründet. Im angefochtenen Urteil wird den Beschwerdeführern ein Verstoss gegen Treu und Glauben vorgeworfen, eine strafrechtlich relevante Verfehlung wird ihnen jedoch nicht angelastet. Das angefochtene Urteil stützt sich im Kostenpunkt mithin auf eine zivilrechtliche Verhaltensnorm, gegen welche die Beschwerdeführer in zivilrechtlich vorwerfbarer Weise verstossen und dadurch die Einleitung des Strafverfahrens veranlasst haben sollen. Insoweit lässt sich dem angefochtenen Beschluss weder direkt noch indirekt ein Vorwurf einer strafrechtlichen Schuld entnehmen. Zu prüfen ist jedoch, ob die Vorinstanz willkürfrei schliessen konnte, die Beschwerdeführer hätten gegen Treu und Glauben verstossen, indem sie den Banken relevante Dokumente vorenthalten hätten.
Die Vorinstanz hat willkürfrei festgestellt, die Beschwerdeführer hätten im November 2003 vom Testament von Z._ vom 2. Juli 2003 Kenntnis gehabt. Mit diesem Testament setzte die Erblasserin W._ als Testamentsvollstrecker ein und vermachte dem Comité International zusätzlich zu ihrem Versprechen vom 23. Juni 2002 über Fr. 2'500'000.-- weitere Fr. 3'000'000.--. In tatsächlicher Hinsicht erstellt ist weiter, dass die Beschwerdeführer dieses Testament und die notarielle Urkunde vom 22. Januar 2004 bei ihren Ersuchen an die Walliser und an die Zuger Kantonalbank vom 18. und 24. März 2004, die Konten der Erblasserin zu saldieren und ihnen den Saldo zu überweisen, nicht vorlegten. Mit ihrem Vorgehen erreichten die Beschwerdeführer, dass die Banken die Überweisungen umgehend, nämlich am 29. respektive am 30. März 2004, ausführten.
Entgegen dem Vorbringen der Beschwerdeführer ist die Vorinstanz nicht in Willkür verfallen, wenn sie gefolgert hat, bei Vorlage des Testaments vom 2. Juli 2003 und dem Wissen um die Einsetzung von W._ als Testamentsvollstrecker hätten die Banken vor der Saldierung der Konten zumindest weitere Abklärungen insbesondere zu den Befugnissen des Testamentsvollstreckers getätigt. Dies gilt umso mehr, als sich gemäss "Erbenschein" vom 7. Oktober 2003 die Nachlassabwicklung in der Schweiz nach schweizerischem Recht richtet, sodass jedenfalls nicht gesagt werden kann, die Anwendung monegassischen Rechts, gemäss welchem dem Testamentsvollstrecker keine Verfügungsbefugnis zukommt, sei unbestritten; wäre aber schweizerisches Recht anwendbar, würden dem Willensvollstrecker weitgehende Kompetenzen zustehen.
Das Vorgehen der Beschwerdeführer, nämlich sich ohne Absprache mit dem Testamentsvollstrecker an die Banken zu wenden und diese unter bewusster Vorenthaltung des Testaments vom 2. Juli 2003 zur umgehenden Saldierung der Konten der Erblasserin und zur Überweisung der Gelder auf ihre Konten anzuhalten, kann nicht anders gedeutet werden, als dass die Beschwerdeführer die Banken hierdurch von berechtigten Abklärungen abhalten wollten. Wenn die Vorinstanz dieses Verhalten als Verstoss gegen Treu und Glauben und damit als zivilrechtlich vorwerfbar qualifiziert, so verletzt dies kein Bundesrecht. Daran ändert nichts, dass die Gültigkeit des Testaments vom 2. Juli 2003 zum Zeitpunkt der Bankersuchen infolge Anfechtung noch nicht feststand.
Nicht zu beanstanden ist auch der Schluss der Vorinstanz, das von den Beschwerdeführern gewählte treuwidrige Vorgehen habe den dringenden Tatverdacht begründet, sie wollten den begünstigten Vermächtnisnehmern die ihnen zustehenden Vermögenswerte entziehen, sodass sich die Staatsanwaltschaft veranlasst gesehen habe, der Sache nachzugehen. Die Durchführung einer Strafuntersuchung rechtfertigte sich auch deshalb, weil - wie den Beschwerdeführern bewusst war - ein komplizierter internationaler Sachverhalt vorliegt, die Rechtslage bezogen auf die Frage des anwendbaren Rechts unklar ist und es um die Ausrichtung von Vermächtnissen in der Höhe von mehreren Millionen Franken geht bzw. ging.
Zusammenfassend konnte die Vorinstanz damit, ohne gegen Bundesrecht zu verstossen, folgern, die Beschwerdeführer hätten sich durch eine Missachtung des Grundsatzes von Treu und Glauben zivilrechtlich vorwerfbar verhalten und hierdurch die Einleitung der gegen sie geführten Strafuntersuchung adäquat kausal verursacht. Der Betrag der überbundenen Verfahrenskosten von insgesamt Fr. 2'800.-- erscheint ohne Weiteres angemessen, was von den Beschwerdeführern auch nicht bestritten wird. Eine willkürliche Anwendung der kantonalen Kostenbestimmung von <ref-law>/VS liegt nach dem Gesagten nicht vor.
4. 4.1 Die Beschwerden sind daher abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang sind die Kosten des bundesgerichtlichen Verfahrens von insgesamt Fr. 4'000.-- den Beschwerdeführern je zur Hälfte aufzuerlegen (<ref-law>).
4.2 Die Aufsichtskommission über die Rechtsanwälte des Kantons Zug hat, wie erwähnt, um Zustellung des bundesgerichtlichen Urteils ersucht.
Gemäss <ref-law> melden die eidgenössischen Gerichtsbehörden der Aufsichtsbehörde des Kantons, in dem eine Anwältin oder ein Anwalt eingetragen ist, unverzüglich das Fehlen persönlicher Voraussetzungen nach <ref-law> sowie Vorfälle, welche die Berufsregeln verletzen könnten.
Da das zivilrechtlich vorwerfbare Verhalten des Beschwerdeführers 1 einen Verstoss gegen die Berufsregeln begründen könnte, ist dem Ersuchen der kantonalen Aufsichtskommission zu entsprechen.

Demnach erkennt das Bundesgericht:
1. Die Verfahren 1B_39/2012 und 1B_43/2012 werden vereinigt.
2. Die Beschwerden werden abgewiesen, soweit darauf einzutreten ist.
3. Die Gerichtskosten von insgesamt Fr. 4'000.-- werden den Beschwerdeführern je zur Hälfte auferlegt.
4. Dieses Urteil wird den Beschwerdeführern, der Staatsanwaltschaft und dem Kantonsgericht des Kantons Wallis, I. Strafrechtliche Abteilung, und der Aufsichtskommission über die Rechtsanwälte des Kantons Zug schriftlich mitgeteilt.
Lausanne, 10. Mai 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Stohner