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 (<ref-law>), der Rechtsweggarantie (<ref-law>) 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.

Erwägungen:
1. Das Bundesgericht prüft seine Zuständigkeit und die Eintretensvoraussetzungen von Amtes wegen und mit freier Kognition (<ref-law>; <ref-ruling> E. 1.1 S. 3 mit Hinweisen).
2. Dem von der kantonalen Steuerverwaltung angefochtenen Entscheid des Verwaltungsgerichts liegt ein Entscheid der Steuerrekurskommission zu Grunde, mit welchem die Sache zur Durchführung des Einspracheverfahrens an die Steuerverwaltung zurückgewiesen wurde. Das Verwaltungsgericht trat auf die Beschwerde gegen den Steuerrekurskommissionsentscheid mangels Beschwerdelegitimation der kantonalen Steuerverwaltung nicht ein. Die Frage, ob es sich dabei um einen End- oder Zwischenentscheid handelt, kann offengelassen werden: Die Steuerverwaltung kann den Nichteintretensentscheid des Verwaltungsgerichts anfechten, gleichgültig ob dieser als End- oder Zwischenentscheid zu qualifizieren ist (vgl. Art. 90 und 93 Abs. 1 lit. a BGG; <ref-ruling> E. 1.3 S. 127 f.; Urteil 2C_258/2008 vom 27. März 2009 E. 3 mit Hinweisen), da die Voraussetzung des nicht wieder gutzumachenden Nachteils gemäss <ref-law> erfüllt ist (vgl. <ref-ruling> E. 5 S. 482 ff.; <ref-ruling> E. 1.2 S. 412; je mit Hinweisen).
Da auch die Frist- und Formvorschriften (vgl. Art. 42 und 100 BGG) eingehalten sind, erweist sich die Beschwerde als zulässig, sofern auch die Legitimationsvoraussetzungen (vgl. E. 3 und 4 hiernach) erfüllt sind.
3. Die Beschwerdeführerin stützt ihre Legitimation zunächst auf Art. 50 Abs. 3 in Verbindung mit Art. 73 des Bundesgesetzes vom 14. Dezember 1990 über die Harmonisierung der direkten Steuern der Kantone und Gemeinden (Steuerharmonisierungsgesetz, StHG; SR 642.14) und <ref-law>.
3.1 Gemäss <ref-law> sind zur Beschwerde in öffentlich-rechtlichen Angelegenheiten Personen, Organisationen und Behörden berechtigt, denen ein anderes Bundesgesetz dieses Recht einräumt.
Gemäss Art. 73 Abs. 1 StHG unterliegen Entscheide der letzten kantonalen Instanz, die eine in den Titeln 2-5 und 6 Kapitel 1 geregelte Materie betreffen, nach Massgabe des Bundesgerichtsgesetzes der Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Beschwerdeberechtigt sind nach Art. 73 Abs. 2 StHG die Steuerpflichtigen, die nach kantonalem Recht zuständige Behörde und die Eidgenössische Steuerverwaltung. Art. 73 Abs. 2 StHG bildet grundsätzlich einen Anwendungsfall von <ref-law> (vgl. BERNHARD WALDMANN, in: Basler Kommentar zum Bundesgerichtsgesetz, 2008, Art. 89 N 68).
Art. 50 Abs. 3 StHG hält (unter dem Fünften Titel "Verfahrensrecht", welcher in den Anwendungsbereich von Art. 73 StHG fällt) fest, dass die kantonale Steuerverwaltung den Rekursentscheid an eine weitere verwaltungsunabhängige kantonale Instanz, hier das Verwaltungsgericht, ziehen kann, wenn das kantonale Recht dies vorsieht. Art. 201 Abs. 2 des Steuergesetzes [des Kantons Bern] vom 21. Mai 2000 (StG/BE; BSG 661.11) hält fest, dass die kantonale Steuerverwaltung zur Beschwerde gegen Rekursentscheide an das Verwaltungsgericht befugt ist.
3.2 Die Steuerverwaltung kann somit vor dem Bundesgericht geltend machen, das Verwaltungsgericht sei in Verletzung von Art. 50 Abs. 3 StHG resp. Art. 201 Abs. 2 StG/BE nicht auf ihre Beschwerde eingetreten. Bei der Frage, ob das kantonale Steuergesetz einen solchen Weiterzug vorsieht, handelt es sich grundsätzlich um die Auslegung von kantonalem Recht; dessen Anwendung kann das Bundesgericht nicht frei, sondern in einem Fall wie hier im Wesentlichen nur auf Verfassungskonformität prüfen (vgl. <ref-law>). In diesem Zusammenhang steht die Rüge des Willkürverbots im Vordergrund (Zur Möglichkeit der Steuerverwaltung, die Verletzung verfassungsmässiger Rechte zu rügen: <ref-ruling> E. 3.3 S. 132 f. mit Hinweisen).
Das Willkürverbot räumt nicht nur dem Einzelnen im Sinne eines Grundrechts einen Anspruch auf willkürfreie Anwendung der seine Rechtsposition betreffenden Normen ein, sondern es beansprucht auch Geltung als objektives, für die gesamte Staatstätigkeit verbindliches Grundprinzip (<ref-ruling> E. 1.4.4 S. 41 f.). Gestützt auf diesen objektiv-rechtlichen Gehalt von <ref-law> kann die kantonale Steuerverwaltung daher vorliegend geltend machen, die Vorinstanz habe das kantonale Recht willkürlich ausgelegt und angewendet.
3.2.1 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung dann vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist; dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 1.2 S. 177; <ref-ruling> E. 3.1 S. 473 f., je mit Hinweisen).
3.2.2 Ob die Vorinstanz das kantonale Recht (Art. 201 StG/BE) geradezu willkürlich ausgelegt hat, ist wohl eher zu verneinen. Sie hat im angefochtenen Entscheid sachliche und durchaus vertretbare Argumente für die Auslegung von Art. 201 Abs. 2 StG/BE gegen den Wortlaut angeführt, womit der Entscheid auf einer möglichen und nicht unhaltbaren Auslegung des kantonalen Rechts zu beruhen scheint. Es versteht sich im Übrigen nicht von selbst, dass eine Verwaltungsbehörde fehlerhafte Entscheide einer Rechtsmittelinstanz anfechten kann. Vielmehr bedarf es dazu in der Regel einer ausdrücklichen Ermächtigung im Gesetz und es steht auch nichts entgegen, einer Behörde die Beschwerdeberechtigung nur beschränkt zu gewähren. Die Frage, ob die Vorinstanz das kantonale Recht willkürlich ausgelegt hat, kann hier indes offen gelassen werden, da sich die Legitimation der Beschwerdeführerin - wie nachfolgend unter E. 4 aufgezeigt wird - ohnehin aus anderen Überlegungen ergibt.
3.3 Die Beschwerdeführerin beruft sich zudem auf die Rechtsweggarantie und macht geltend, die Auslegung von Art. 201 Abs. 2 StG/BE durch die Vorinstanz verletze Bundesverfassungsrecht (<ref-law>) sowie kantonales Verfassungsrecht (Art. 26 KV/BE). Sie legt allerdings nicht dar, inwieweit ihr das kantonale Verfassungsrecht einen weitergehenden Schutz gewährleisten sollte als die Bundesverfassung. Damit ist der angefochtene Entscheid einzig auf Vereinbarkeit mit dem Bundesverfassungsrecht zu prüfen.
Hinsichtlich der Verletzung von Grundrechten (und von kantonalem und interkantonalem Recht) gilt eine qualifizierte Rügepflicht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.2 S. 254). Eine diesen Anforderungen genügende Begründung ist hier nicht zu erkennen: Die Beschwerdeführerin behauptet zwar eine Verletzung der Rechtsweggarantie, legt aber nicht rechtsgenüglich dar, inwiefern der angefochtene Entscheid gegen dieses Grundrecht verstossen soll. Eine qualifizierte Begründung liegt hier somit nicht vor; insoweit kann auf die Beschwerde nicht eingetreten werden.
4. Die Beschwerdeführerin bringt weiter vor, ihre Beschwerdelegitimation ergebe sich - unabhängig von den kantonalen Ausführungsbestimmungen zu Art. 50 Abs. 3 StHG (vgl. E. 3.1 und 3.2 hiervor) - aus <ref-law> in Verbindung mit Art. 73 StHG (und <ref-law>). Sie macht geltend, auch ein bloss formaler Bezug zum Steuerharmonisierungsrecht genüge, um der nach kantonalem Recht zuständigen Behörde die Legitimation zur Beschwerde ans Bundesgericht zu verleihen.
4.1 <ref-law> umschreibt in Fortführung von Art. 98a des früheren Bundesrechtspflegegesetzes vom 16. Dezember 1943 (OG) den Grundsatz der Einheit des Verfahrens: Wer zur Beschwerde an das Bundesgericht berechtigt ist, muss sich am Verfahren vor allen kantonalen Vorinstanzen als Partei beteiligen können (<ref-law>); die unmittelbare Vorinstanz des Bundesgerichts muss grundsätzlich mindestens die Rügen nach den Artikeln 95-98 BGG prüfen können (<ref-law>). Aus diesen Bestimmungen ergibt sich, dass die kantonalen Behörden die Rechtsmittelbefugnis nicht enger fassen dürfen, als sie für die Beschwerde an das Bundesgericht umschrieben ist. Zur Beurteilung, ob das Verwaltungsgericht die Beschwerdeführerin vom Rechtsmittel ausschliessen durfte, ist daher die Beschwerdeberechtigung nach den Grundsätzen von <ref-law> in Verbindung mit Art. 73 StHG zu prüfen. Wäre die Beschwerdeführerin befugt, gegen den angefochtenen Entscheid beim Bundesgericht in der Sache Beschwerde zu führen, so hätte auch das Verwaltungsgericht auf ihr Rechtsmittel eintreten müssen (vgl. etwa <ref-ruling> E. 5 S. 149).
4.2 Gemäss Art. 4 Abs. 1 und 21 Abs. 1 lit. b StHG begründet das Unterhalten von Betriebsstätten für natürliche wie juristische Personen eine "Steuerpflicht aufgrund wirtschaftlicher Zugehörigkeit". Diese Bestimmungen befinden sich im Zweiten bzw. Dritten Teil des Steuerharmonisierungsgesetzes und fallen damit grundsätzlich in den Anwendungsbereich von Art. 73 StHG. Das Bundesgericht ist denn auch auf eine Beschwerde einer kantonalen Steuerverwaltung betreffend der Frage der Betriebsstättenqualität von Tankstellen - im Zusammenhang mit einer interkantonalen Doppelbesteuerungsangelegenheit - eingetreten, da es den bloss formalen Bezug zum Steuerharmonisierungsrecht, wie er bei Fragen der subjektiven Steuerpflicht letztlich immer gegeben ist, als genügend betrachtete (<ref-ruling> E. 1.2 S. 306).
4.3 Die Vorinstanz vertritt die Auffassung, ein solcher formaler Bezug zum Steuerharmonisierungsrecht fehle im vorliegenden Fall, da die interkommunale Steuerteilung gemäss Art. 252 ff. StG/BE nicht zu den in den Titeln 2-5 und 6 Kapitel 1 des StHG geregelten Materien gehöre; das StHG regle weder in materieller noch formeller Hinsicht, ob und wie eine interkommunale Steuerteilung vorzunehmen sei. Die Steuerteilung beruhe demnach gänzlich auf kantonalem Recht und der Betriebsstättenbegriff gelange im Rahmen von Art. 254 StG/BE ausschliesslich "autonom-kantonalrechtlich" zur Anwendung (vgl. E. 3.6.2 des angefochtenen Entscheides), was zum Ausschluss der Beschwerdebefugnis der kantonalen Steuerverwaltung führen müsse.
4.4 Die Argumentation der Vorinstanz vermag nicht zu überzeugen: Es trifft zwar zu, dass die Steuerteilung unter den bernischen Gemeinden gemäss Art. 252 ff. StG/BE von der Steuerharmonisierung ausgenommen ist und die diesbezüglichen Normen, insbesondere Art. 254 StG/BE, keinen unmittelbaren Bezug zum StHG haben, was die Behördenbeschwerde gemäss Art. 73 Abs. 2 StHG ausschliessen könnte. Indessen darf nicht übersehen werden, dass Art. 254 StG/BE an den Betriebsstättenbegriff anknüpft, wie er in Art. 5 resp. Art. 77 StG/BE - gestützt auf die harmonisierungsrechtlichen Normen von Art. 4 resp. Art. 21 StHG - umschrieben ist. Rechtsbegriffe sind wegen der Rechtssicherheit grundsätzlich für die ganze Rechtsordnung - zumindest aber im selben kantonalen Erlass - gleich auszulegen (vgl. <ref-ruling> E. 2a S. 185). Mit der Qualifikation einer Einrichtung als Betriebsstätte gestützt auf Art. 254 StG/BE sind daher notwendigerweise auch die entsprechenden, harmonisierten Begriffe von Art. 5 und 77 StG/BE resp. Art. 4 und 21 StHG angesprochen.
Dazu kommt, dass sich hier das Auslegungsergebnis direkt (und nicht etwa nur mittelbar) auf die subjektive Steuerpflicht der Steuerpflichtigen (E._ AG) auswirkt. Für diese resultieren, je nach steuerrechtlicher Qualifikation ihrer Warenverkaufsautomaten als Betriebsstätten und entsprechender Zuordnung zu einer bestimmten Gemeinde, aufgrund der jeweiligen Steuersätze unterschiedliche Steuerbelastungen. Zudem wäre es widersprüchlich, eine Einrichtung im Rahmen der interkantonalen Festlegung der Steuerpflicht aufgrund ihres Umfangs als Betriebsstätte zu qualifizieren, sie bei der innerkantonalen Steuerteilung aber - in Anwendung des gleichen Rechtsbegriffs - anders zu behandeln. Ein solches Vorgehen könnte, wie die Beschwerdeführerin zu Recht befürchtet, auf die interkantonale Festlegung zurückwirken und diese zumindest für die Folgejahre wieder in Frage stellen. Mit der Anwendung des Betriebsstättenbegriffs gestützt auf Art. 254 StG/BE ist daher Harmonisierungsrecht in nicht bloss nebensächlichem Umfang mitbetroffen, weshalb insoweit selbst bei der Steuerteilung nicht - wie dies die Vorinstanz getan hat - von einem völlig autonomen, von der Harmonisierung ausgenommenen Regelungsbereich gesprochen werden kann. Vielmehr steht vorliegend Harmonisierungsrecht in einem Ausmass mit in Frage, dass ein hinreichender formaler Bezug zum Steuerharmonisierungsrecht (<ref-ruling> E. 1.2 S. 306; vgl. auch <ref-ruling> E. 2 S. 128 ff.) gegeben ist.
4.5 Daraus folgt, dass die Legitimation der Beschwerdeführerin zur öffentlich-rechtlichen Beschwerde ans Bundesgericht in der Sache selbst zu bejahen ist, was ihr gemäss <ref-law> auch den innerkantonalen Beschwerdeweg öffnet (vgl. E. 4.1). Die Vorinstanz hätte somit auf die Beschwerde der kantonalen Steuerverwaltung eintreten und diese in materieller Hinsicht prüfen müssen.
5. Es ergibt sich, dass die vorliegende Beschwerde begründet und gutzuheissen ist, soweit darauf eingetreten werden kann. Der angefochtene Entscheid ist aufzuheben und die Sache an die Vorinstanz zur weiteren Behandlung zurückzuweisen (<ref-law>, aufgrund dessen Art. 73 Abs. 3 StHG obsolet ist; vgl. <ref-ruling> E. 1.5.3 S. 192).
Bei diesem Ausgang des bundesgerichtlichen Verfahrens sind die Gerichtskosten der Einwohnergemeinde Bolligen als Beschwerdegegnerin aufzuerlegen (Art. 66 Abs. 1 und 4 BGG). Eine Parteientschädigung ist nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist, und das Urteil des Verwaltungsgerichts des Kantons Bern vom 12. März 2009 wird aufgehoben.
2. Die Angelegenheit wird zur materiellen Prüfung an die Vorinstanz zurückgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden der Einwohnergemeinde Bolligen auferlegt.
4. Dieses Urteil wird der Beschwerdeführerin, der Einwohnergemeinde Bolligen, der E._ AG, dem Verwaltungsgericht und der Steuerrekurskommission des Kantons Bern sowie der Eidgenössischen Steuerverwaltung schriftlich mitgeteilt.
Lausanne, 30. Oktober 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Winiger