Sachverhalt:
A. Die Eheleute A. X._ (Eigentümerin) und B. X._ (Eigentümer) sind Eigentümer eines Stockwerkeigentümeranteils über Räumlichkeiten im zweiten Obergeschoss des Geschäftshauses an der Z._strasse in Brig. Die Eigentümerin hatte den Eigentümer zur Vermietung dieser Räumlichkeiten bevollmächtigt. Im Hinblick auf deren Miete nahm die Versicherung Y._ AG, handelnd durch C._, mit den Eigentümern Kontakt auf. Dieser besichtigte die Räumlichkeiten und erhielt vom Eigentümer einen Grundrissplan. In einer E-Mail vom 8. August 2006 führte D._, Prokurist und Projektleiter der Versicherung Y._ gegenüber dem Eigentümer aus, wie telefonisch schon abgemacht, bestätige er, dass die Versicherung Y._ die Räume an der Z._strasse mieten möchte, E._ werde dem Eigentümer einen Vertragsvorschlag senden mit:
" - Mietzins: 2'100./Monat + NK (letzes Jahr, ca. 2'100.-(J)
- Fläche 134m2 + 2 x Balkon
- Keller im UG
- kein Parkplatz (S. 21)."
Am 9. August 2006 wurde der Eigentümerin per E-Mail der allgemein gehaltene Standard-Mietvertrag der Versicherung Y._ zugestellt. Der Eigentümer strich in diesem Vertrag sämtliche Varianten, die nicht zutrafen oder an den gegebenen Lokalitäten nicht möglich waren. Er liess jedoch Ziff. 12.6 Abs. 1 mit folgendem Wortlaut stehen:
"Der vorstehende Mietvertrag wird in zwei gleichlautenden Exemplaren ausgefertigt und unterzeichnet und erlangt erst Rechtsgültigkeit mit Unterzeichnung durch beide Parteien."
Alsdann ergänzte der Eigentümer den Standardvertrag hinsichtlich des Mietobjekts, des jährlichen Mietzinses von Fr. 25'200.-- und sah ab dem 1. September 2006 eine Mietdauer von fünf Jahren mit einer Option für zwei Jahre vor. Am 14. August 2006 sandte er den auf diese Weise ergänzten Mietvertrag derVersicherung Y._ zu.
Nach den Angaben des Eigentümers hat ihm E._ telefonisch erklärt, der Vertrag sei grundsätzlich so in Ordnung, die Versicherung Y._ wünsche jedoch eine Verlängerung der Option um fünf Jahre. Am 18. August 2006 stellte die Versicherung Y._ die Pläne für den beabsichtigten Umbau dem Eigentümer zu. Dieser nahm im Vertrag die von der CS gewünschte Verlängerung der Option um 5 Jahre, die Übernahme der Prämie der Gebäudehaftpflichtversicherung als zusätzliche Nebenkosten und die Rückbaupflicht betreffend den Tresor und verschiedene Wände gemäss den zugestellten Plänen auf und sandte den dadurch abgeänderten Vertrag am 22. August 2006 der Versicherung Y._. Gleichentags übergab er C._ einen Schlüssel zu den Räumlichkeiten, holte diesen am 25. August 2006 bei C._ jedoch wieder ab, um mit dem bisherigen Mieter die Mietabnahme vorzunehmen. Nach der Wohnungsabnahme warf der Eigentümer sämtliche Schlüssel in den Briefkasten der Versicherung Y._. C._ bestätigte, die Schlüssel erhalten zu haben. Noch vor dem 1. September 2006 hatte D._ vom Eigentümer telefonisch verlangt, die Lavabos und die Lichtanlage im Mietobjekt zu entfernen. Am 12. September 2006 sandten die Eigentümer der Versicherung Y._ zu Handen von D._ folgendes Schreiben (act. S. 44).
"Mietvertrag Z._strasse, Brig, 2. OG
Sehr geehrte Herren
Wir stellen fest, dass wir in obiger Angelegenheit den Mietvertrag in Bestätigung der Abmachungen zwischen den Parteien bis heute zur Gegenzeichnung nicht erhalten haben.
Bei uns hat sich F._ am 4.9.2006 erkundigt, ob man gegen Entschädigung bereit wäre, vom Mietvertrag zurückzutreten. Damit waren wir nicht einverstanden. Deshalb hat F._ erklärt, er werde D._ anweisen, uns umgehend die Verträge zur Gegenzeichnung und Bestätigung des abgeschlossenen Mietvertrages zuzustellen, sofern dies nicht bereits geschehen sei. Die Versicherung Y._ hat die Miete auf den 1. September 2006 angetreten.
Wir ersuchen Sie deshalb, uns die Papiere umgehend zuzustellen."
Mit Schreiben vom 29. September 2006 bat die R._ AG den Eigentümer, ein Baugesuch der Versicherung Y._ betreffend die Anbringung einer Reklamebeschriftung an der Z._strasse in Brig schnellstmöglich unterzeichnet zurückzusenden. Dieser Bitte kam der Eigentümer am 2. Oktober 2006 nach. Mit Schreiben vom 26. Oktober 2006 teilte D._ den Eigentümern mit, der Mietvertrag sei trotz weit gediehener Verhandlungen nicht unterzeichnet worden und demnach nicht gültig zustande gekommen.
B. Nach erfolglosem Schlichtungsverfahren klagten die Eigentümer (Kläger) am 16. Mai 2007 beim Bezirksgericht Brig gegen die Versicherung Y._ (Beklagte) auf Zahlung von Mietzinsen von insgesamt Fr. 18'900.-- für die Monate September 2006 bis und mit August 2007 nebst Zins. Zudem verlangten die Kläger Fr. 2'128.85.-- nebst Zins als Ersatz für Verspätungsschaden, Stromkosten und weiteren Schaden. Das Bezirksgericht wies am 26. September 2008 die von der Beklagten erhobene Einrede der örtlichen und sachlichen Unzuständigkeit ab und beschränkte das Verfahren vorerst auf die Frage des Zustandekommens eines Mietvertrages. In ihrer Replik vom 3. November 2008 stellten die Kläger namentlich das Begehren, die Beklagte sei zur Zahlung der Mietzinse vom 1. September 2006 bis und mit 30. September 2008 entsprechend Fr. 52'500.-- zuzüglich Zins zu 5 % seit 1. September 2007 zu verpflichten.
Mit Urteil vom 18. Juni 2010 stellte das Bezirksgericht fest, die Parteien hätten für die Wohnung im zweiten Obergeschoss an der Z._strasse in Brig ab dem 1. September 2006 einen Mietvertrag abgeschlossen. Zur Begründung führte es im Wesentlichen aus, die Parteien seien sich spätestens Ende August 2006 über alle Punkte des überarbeiteten Mietvertrages einig gewesen, und es hätten definitive Pläne für bauliche Anpassungen vorgelegen, die im Auftrag der Beklagten im Anhang des Mietvertrages enthalten waren. Durch die Aushändigung der Schlüssel habe die Übergabe der Mietsache stattgefunden. Zudem hätten die Kläger im Auftrag der Beklagten den vorherigen Mieter angewiesen, die Lampeneinrichtungen zu entfernen. Demnach hätte die Beklagte die Miete gemäss <ref-law> per 1. September 2006 angetreten. Die Kläger hätten daraus, dass sie nach ihrem Schreiben vom 12. September 2006 im Auftrag der Beklagten am 29. September 2009 von der R._ AG zur Unterzeichnung von Baugesuchen aufgefordert wurden, schliessen dürfen, die Beklagte sei selber vom Bestand eines Mietvertrages ausgegangen. Dies habe die Beklagte erstmals mit ihren Schreiben vom 26. Oktober 2006 klar verneint. Am 27. Oktober 2006 habe sie die Wohnungsschlüssel mittels Einschreibebrief retourniert. Namentlich aufgrund der Übernahme der Schlüssel sei der überarbeitete Mietvertrag zustande gekommen. Die Beklagte habe ihn nur deshalb nicht unterzeichnet, weil sie nach Mietantritt ein anderes Angebot erhalten habe. Mithin sei den Klägern der Beweis gelungen, dass der Vorbehalt der Schriftform einzig Beweiszwecken gedient habe.
In Gutheissung einer Berufung der Beklagten hob das Kantonsgericht des Kantons Wallis das erstinstanzliche Urteil am 24. Mai 2012 auf und stellte fest, zwischen den Parteien sei bezüglich der Räumlichkeiten im zweiten Obergeschoss an der Z._strasse, Brig ab dem 1. September 2006 kein Mietvertrag zustande gekommen, und wies die Klage ab.
C. Die Kläger (Beschwerdeführer) erheben Beschwerde in Zivilsachen mit dem sinngemässen Begehren, das Urteil des Kantonsgerichts vom 24. Mai 2012 aufzuheben und das erstinstanzliche Urteil vom 18. Juni 2010 zu bestätigen. Eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Die Beklagte (Beschwerdegegnerin) schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werden kann. Das Kantonsgericht verweist ohne ausdrücklichen Antrag auf sein Urteil.

Erwägungen:
1. Die Beschwerde richtet sich gegen einen verfahrensabschliessenden Entscheid (<ref-law>) einer oberen kantonalen Instanz, die auf ein Rechtsmittel hin kantonal letztinstanzlich in einer Zivilsache entschieden hat (Art. 75 i.V.m. <ref-law>). Die Rechtsbegehren der Beschwerdeführer sind im kantonalen Verfahren nicht geschützt worden (<ref-law>), der massgebende Streitwert beträgt mehr als Fr. 15'000.-- (Art. 51 i.V.m. <ref-law>) und die Beschwerdefrist ist eingehalten (<ref-law>). Auf die Beschwerde kann damit eingetreten werden.
2. 2.1 Nach <ref-law> legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Abs. 1). Es kann diese Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Abs. 2). Wer sich auf eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit Aktenhinweisen darzulegen, dass er entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (Urteile 4A_275/2011 vom 20. Oktober 2011 E. 2, nicht publ. in: <ref-ruling>; 4A_214/2008 vom 9. Juli 2008 E. 1.2, nicht publ. in: <ref-ruling>).
2.2 Die Beschwerdeführer rügen, das Kantonsgericht habe zwar ausgeführt, dass sämtliche Schlüssel in den Briefkasten der Beschwerdegegnerin eingeworfen worden seien. Es habe jedoch im Gegensatz zum Bezirksgericht nicht festgestellt, wann die Schlüssel wieder in den Besitz der Beschwerdeführer gelangt seien, obwohl diese durch die Klagebeilage Nr. 22 belegt hätten, dass dies erst am 30. Oktober 2006 der Fall gewesen sei. Damit verlangen die Beschwerdeführer eine entsprechende Ergänzung des vorinstanzlich festgestellten Sachverhalts.
2.3 Das Bezirksgericht stellte fest, die Schlüssel des Mietobjekts seien den Beschwerdeführern am 27. Oktober 2006 mit eingeschriebener Sendung ohne Kommentar zugesandt worden. Gemäss dem entsprechenden Beleg in den kantonalen Akten (S. 64, Klagebeilage 22) ist die am Freitag, den 27. Oktober 2006 abgesandte Sendung am Montag, den 30. Oktober 2006 eingegangen. Gestützt darauf kann der zweitinstanzlich festgestellte Sachverhalt entsprechend dem Begehren der Beschwerdeführer ergänzt und festgestellt werden, dass die Schlüssel mit eingeschriebener Post vom 27. Oktober 2006 den Eigentümern zurückgesandt wurden.
3. 3.1 Das Kantonsgericht erwog, die E-Mail der Beschwerdegegnerin vom 8. August 2006 zeige bloss die Bereitschaft, einen Mietvertrag abzuschliessen, nicht jedoch, dass ein solcher bereits abgeschlossen worden sei. Die Beschwerdegegnerin habe den in Ziff. 12.6 ihres Mustervertrages als Gültigkeitsvoraussetzung vorgesehenen Vorbehalt der Schriftform gewollt. Die Beschwerdeführer seien erfahrene Juristen und hätten sich daher der Tragweite dieses Vorbehalts bewusst sein müssen. Der Beschwerdeführer habe diesem zugestimmt, indem er den von ihm abgeänderten Mustervertrag mit diesem Vorbehalt am 14. August 2006 an die Versicherung Y._ gesandt habe. Auch nach der nochmaligen Abänderung des Vertrages vom 22. August 2006 durch den Beschwerdeführer sei der Vorbehalt noch enthalten und damit gewollt gewesen. An der Tatsache, dass der Mietvertrag erst Gültigkeit erlangen sollte, wenn er gegenseitig unterzeichnet war, ändere auch nichts, dass die Beschwerdegegnerin von den Beschwerdeführern noch die Entfernung der Lavabos und der Lichtanlage verlangt und sie um Unterzeichnung eines Gesuches betreffend Reklameschild ersucht habe.
3.2 Die Beschwerdeführer machen zusammengefasst geltend, die Parteien seien sich über den Abschluss des Mietvertrages gemäss der Fassung vom 22. August 2006 einig gewesen und hätten durch konkludentes Verhalten, namentlich die Übergabe bzw. Übernahme der Schlüssel zum Mietobjekt und die seitens der Beschwerdeführerin erfolgte Anweisung zur Entfernung der Lichtanlage und der Lavabos im Mietobjekt, auf den Formvorbehalt verzichtet.
3.3 Ist für einen Vertrag, der vom Gesetze an keine Form gebunden ist, die Anwendung einer solchen vorbehalten worden, so wird gemäss <ref-law> vermutet, dass die Parteien vor Erfüllung der Form nicht verpflichtet sein wollen. Diese Vermutung kann durch den Nachweis widerlegt werden, dass die Parteien nachträglich durch konkludentes Verhalten auf die vorbehaltene Form verzichtet haben (<ref-ruling> E. 4c S. 268 mit Hinweisen). Ein konkludenter Verzicht ist namentlich anzunehmen, wenn die Parteien vor der Erfüllung der Form vertragliche Leistungen vorbehaltlos erbringen und entgegennehmen (<ref-ruling> E. 1 S. 78; Urteil 4C.362/1994 vom 28. März 1995 E. 3b/cc). Ist der Kauf des Ladeninventars Voraussetzung für den Abschluss eines Mietvertrages, belegt die Mitteilung des künftigen Mieters an den Vermieter, der Kaufvertrag über das Inventar sei zustande gekommen, dass der neue Mieter sich schon vor der Erfüllung der vereinbarten Schriftform gebunden wissen wollte (Urteil C.11/1984 vom 12. April 1984 E. 3).
3.4 Im vorliegenden Fall haben die Beschwerdeführer ihre vertragliche Leistung erbracht, indem sie der Beschwerdegegnerin noch vor Beginn der Miete am 1. September 2006 die Schlüssel zum Mietobjekt übergaben und damit die tatsächliche Nutzungsmöglichkeit verschafften. Die Beschwerdegegnerin hat diese Schlüssel vorbehaltlos angenommen und erst am 27. Oktober 2007 wieder zurückgesendet. Zudem hat sie nach Erhalt des Mietvertrages vom 22. August 2006 die Beschwerdeführer angewiesen, im Mietobjekt die Lampen und Lavabos zu entfernen, worauf die Beschwerdeführer die Lichtanlage abmontieren liessen. Mit diesen Handlungen, welche der Erfüllung bzw. Umsetzung des Vertrages dienten, haben die Parteien zum Ausdruck gebracht, dass sie bereits vor der Unterzeichnung des schriftlichen Mietvertrages von dessen Rechtsgültigkeit ausgingen und auf die Schriftform als Gültigkeitsvoraussetzung verzichteten. Die Vorinstanz hat daher Bundesrecht verletzt, indem sie in Abweichung vom erstinstanzlichen Urteil vom 18. Juni 2010 aufgrund der Nichterfüllung der Schriftform das Zustandekommen eines Mietvertrages verneinte. Demnach ist das angefochtene Urteil in Gutheissung der Beschwerde aufzuheben und das erstinstanzliche Urteil zu bestätigen.
3.5 Mit der Aufhebung des angefochtenen Urteils werden die weiteren von den Beschwerdeführern dagegen gerichteten Rügen gegenstandslos.
4. Gemäss dem Ausgang des bundesgerichtlichen Verfahrens wird die unterliegende Beschwerdegegnerin dafür kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG). Die Sache ist zu neuer Entscheidung über die Kosten- und Entschädigungsfolgen des kantonalen Rechtsmittelverfahrens an die Vorinstanz zurückzuweisen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. In Gutheissung der Beschwerde wird das Urteil des Kantonsgerichts des Kantons Wallis vom 24. Mai 2012 aufgehoben und festgestellt, dass die Parteien für die Wohnung im zweiten Obergeschoss an der Z._strasse in Brig ab dem 1. September 2006 einen Mietvertrag abgeschlossen haben.
2. Die Sache wird zu neuer Entscheidung über die Kosten- und Entschädigungsfolgen des kantonalen Rechtsmittelverfahrens an die Vorinstanz zurückgewiesen.
3. Die Gerichtskosten von Fr. 2'500.-- werden der Beschwerdegegnerin auferlegt.
4. Die Beschwerdegegnerin hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit insgesamt Fr. 3'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Kantonsgericht des Kantons Wallis, I. zivilrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 21. November 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Gelzer