Sachverhalt: A. Die E._ AG (im Folgenden: AG) ist eine Aktiengesellschaft mit Sitz in A._/VS. Sie bezweckt den Erwerb und Betrieb, die Förderung und den Verkauf von Hotels und Hotelbeteiligungen sowie den Erwerb und Betrieb von Sportartikelbetrieben, den Kauf, die Vermietung und den Verkauf von Sportartikeln aller Art. Zudem kann sie alle geschäftlichen und finanziellen Tätigkeiten auch auf dem Gebiet von Mobilien und Immobilien ausüben, kann Grundstücke und Immaterialgüterrechte erwerben, verwalten, belasten, verwerten und verkaufen sowie andere Gesellschaften finanzieren und Zweigniederlassungen errichten. Das Aktienkapital beträgt Fr. 240'000.-- und ist in 240 Aktien à Fr. 1'000.-- gestückelt. Bei der Gründung übernahm die AG mit Sacheinlagevertrag vom 9. März 2005 von der Einzelfirma "D._" unter anderem drei Grundstücke in A._/VS. Am 6. Februar 2006 übertrug Z._ seinen Söhnen Y._ 118 Aktien und X._ 119 Aktien der E._ AG. Die kantonale Dienststelle der Grundbuchämter und der Geomatik setzte am 1. April 2008 - nach Einholen diverser Unterlagen - in zwei getrennten Verfügungen für X._ und Y._ eine Handänderungssteuer (sogenannter Wertstempel gemäss dem kantonalen Stempelgesetz) von Fr. 20'588.-- resp. Fr. 20'415.-- fest. B. Gegen diese Veranlagungen erhoben X._ und Y._ mit getrennten Eingaben Beschwerde beim Staatsrat des Kantons Wallis und bestritten die Voraussetzungen für die Erhebung einer Handänderungssteuer. Mit Entscheiden vom 7. Januar resp. 12. Januar 2009 wies der Staatsrat die Beschwerden kostenpflichtig ab. Die zwei gleichlautenden Beschwerden der Steuerpflichtigen wies das Kantonsgericht des Kantons Wallis, öffentlichrechtliche Abteilung, mit Urteil vom 24. April 2009 ab. C. Mit "Verwaltungsgerichtsbeschwerde" (recte: Beschwerde in öffentlich-rechtlichen Angelegenheiten) vom 29. Mai 2009 beantragen X._ und Y._, das Urteil des Kantonsgerichts sei aufzuheben und es sei festzustellen, dass vorliegend keine Handänderungssteuer geschuldet sei. Gerügt wird eine willkürliche Auslegung des kantonalen Stempelgesetzes durch die rechtsanwendende Behörde. D. Die kantonale Dienststelle der Grundbuchämter und der Geomatik verzichtet auf eine Vernehmlassung. Der Staatsrat und das Kantonsgericht des Kantons Wallis verzichten auf eine Stellungnahme, beantragen aber unter Hinweis auf den angefochtenen Entscheid die Abweisung der Beschwerde. 