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 Art. 256 OR 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. 