Sachverhalt: A. Die E._ AG mit Sitz in R._/FR unterhält Niederlassungen in mehreren Kantonen, so auch in der Gemeinde Bolligen/BE. Sie betreibt in mehreren Kantonen - wie auch in diversen Gemeinden des Kantons Bern - Getränke- und Warenverkaufsautomaten. Die in den bernischen Gemeinden betriebenen Automaten werden grösstenteils von der Niederlassung in Bolligen/BE aus verwaltet. Die Steuerverwaltung des Kantons Bern veranlagte am 13. Dezember 2004 die E._ AG für die Kantons- und Gemeindesteuern der Steuerperiode vom 1. Oktober 2001 bis 30. September 2002 auf einen steuerbaren Gewinn von Fr. 1'995'300.-- zum Satz von Fr. 20'100'700.-- und auf ein steuerbares Kapital von Fr. 672'000.-- zum Satz von Fr. 23'240'000.--. Bestandteil dieser Veranlagungsverfügung bildete ein Teilungsplan für die Steuerteilung unter den bernischen Gemeinden, worin die Steuerverwaltung den im Kanton Bern steuerbaren Gewinn zu 18,6 % und das steuerbare Kapital zu 53,274 % der Einwohnergemeinde Bolligen/BE und den Rest weiteren 168 Gemeinden zuteilte. Die Steuerverwaltung betrachtete dabei die Warenautomaten als Betriebsstätten, welche eine beschränkte Steuerpflicht der E._ AG in den entsprechenden Gemeinden begründeten. B. Gegen den Steuerteilungsplan erhob die Einwohnergemeinde Bolligen/BE mit Schreiben vom 17. Dezember 2004 resp. 4. Februar 2005 Einsprache und machte geltend, der gesamte im Kanton Bern steuerbare Gewinn sei der Betriebsstätte in Bolligen/BE zuzuweisen oder die Teilung sei eventualiter auf "wenige Betriebsstättengemeinden" zu reduzieren. Die Steuerverwaltung wies die Einsprache am 13. April 2006 ab. Gegen die Einspracheverfügung erhob die Einwohnergemeinde Bolligen/BE Rekurs an die Steuerrekurskommission des Kantons Bern. Diese hiess mit Entscheid vom 13. Februar 2007 den Rekurs teilweise gut, hob die angefochtene Einspracheverfügung auf und wies die Akten zur Durchführung des Einspracheverfahrens an die Steuerverwaltung zurück. Die Steuerrekurskommission erwog im Wesentlichen, die Auslegung der Steuerverwaltung, wonach jeder Verkaufsautomat eine Betriebsstätte darstelle, sei "unsinnig" und könne nicht geschützt werden. Die Steuerverwaltung werde nach Abklärung des Sachverhalts im Rahmen des ihr zustehenden Veranlagungsermessens darüber zu befinden haben, wo sie die Untergrenze der noch zu erfassenden Erträge ziehen wolle. Mit Schreiben vom 21. März 2007 erhob die Steuerverwaltung des Kantons Bern gegen den Entscheid der Steuerrekurskommission Beschwerde an das Verwaltungsgericht des Kantons Bern. Mit Urteil vom 12. März 2009 trat das Verwaltungsgericht - im Wesentlichen mit der Begründung, weder das kantonale Steuergesetz noch das Bundesrecht begründe ein Beschwerderecht für die kantonale Steuerverwaltung - auf die Beschwerde nicht ein. C. Mit Eingabe vom 17. April 2009 erhebt die Steuerverwaltung des Kantons Bern Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragt, das Urteil des Verwaltungsgerichts sei aufzuheben und das Verwaltungsgericht sei aufzufordern, auf die Verwaltungsgerichtsbeschwerde der Steuerverwaltung vom 21. März 2007 einzutreten und diese materiell zu beurteilen. Gerügt wird eine Verletzung des Steuerharmonisierungsgesetzes, des Willkürverbots (Art. 9 BV), der Rechtsweggarantie (Art. 29a BV) sowie von kantonalem Verfassungsrecht (Art. 11 und 26 KV/BE). D. Das Verwaltungsgericht des Kantons Bern beantragt die Abweisung der Beschwerde. Während die Einwohnergemeinde Bolligen/BE auf eine Vernehmlassung verzichtet, beantragt die Eidgenössische Steuerverwaltung die Gutheissung der Beschwerde. Die E._ AG verzichtet in Bezug auf die in Frage stehende Legitimation der kantonalen Steuerverwaltung auf eine Stellungnahme.