8.1.1 Das Verfahren ist kostenpflichtig (Art. 65 f. BGG). Nach Art. 66 Abs. 1 BGG werden die Gerichtskosten in der Regel der unterliegenden Partei auferlegt. Dem Bund, den Kantonen und den Gemeinden sowie den mit öffentlich-rechtlichen Aufgaben betrauten Organisationen dürfen in der Regel keine Gerichtskosten auferlegt werden, wenn sie in ihrem amtlichen Wirkungskreis und, ohne dass es sich um ihr Vermögensinteresse handelt, das Bundesgericht in Anspruch nehmen oder wenn gegen ihre Entscheide in solchen Angelegenheiten Beschwerde geführt worden ist (Art. 66 Abs. 4 BGG). Es stellt sich demnach die Frage, ob den unterliegenden Bezirken und Gemeinden die Gerichtskosten aufzuerlegen sind.

8.1.2 Bereits unter dem alten Recht durften gemäss Art. 156 Abs. 2 des Bundesgesetzes vom 16. Dezember 1943 über die Organisation der Bundesrechtspflege (OG; BS 3 574) "dem Bund, Kantonen oder Gemeinden, die in ihrem amtlichen Wirkungskreis und ohne dass es sich um ihr Vermögensinteresse handelt, das Bundesgericht in Anspruch nehmen, oder gegen deren Verfügungen in solchen Angelegenheiten Beschwerde geführt worden ist", in der Regel keine Gerichtskosten auferlegt werden. Nach der Rechtsprechung hatten als Arbeitgeber in ihren Vermögensinteressen betroffene Gemeinden unter der Herrschaft des OG in personalrechtlichen Streitigkeiten grundsätzlich allfällige Gerichtskosten zu tragen (BGE 124 I 223 E. 3 S. 230; 2P.137/2005 vom 17. Oktober 2005 E. 5; 2P.104/2004 vom 14. März 2005 E. 9.1.1; 2P.133/2001 vom 6. September 2001 E. 3). Eine Ausnahme bildete indessen beispielsweise Art. 13 Abs. 5 des Bundesgesetzes vom 24. März 1995 über die Gleichstellung von Frau und Mann (Gleichstellungsgesetz, GlG; SR 151.1), welcher in der bis 31. Dezember 2006 gültig gewesenen Fassung ausdrücklich Kostenfreiheit vorsah. Kostenfrei waren zudem auch personalrechtliche Streitigkeiten, welche keine vermögensrechtlichen Interessen der Gemeinde tangierten (Urteil 2P.46/2006 vom 7. Juni 2006 E. 5).

8.1.3 Die Grundsätze der Kostentragungspflicht vor Bundesgericht (Art. 66 BGG) sind weitgehend vom bisherigen Recht übernommen worden (Botschaft des Bundesrates vom 28. Februar 2001, BBl 2001 4202, 4305 Ziff. 4.1.2.10; BGE 133 V 642 E. 5.3 S. 463). Kostenpflichtig ist gemäss Art. 66 BGG grundsätzlich die unterliegende (Abs. 1) oder die unnötig Kosten verursachende (Abs. 3) Partei. Diese Regel kennt ausdrücklich erwähnte Ausnahmen: Von den Gerichtskosten befreit sind Bund, Kantone und Gemeinden sowie - neu - die mit öffentlich-rechtlichen Aufgaben betrauten Organisationen, sofern sie in ihrem amtlichen Wirkungskreis handeln und es nicht um ihr Vermögensinteresse geht (Abs. 4). Diese drei Voraussetzungen müssen kumulativ erfüllt sein (BERNARD CORBOZ, in: Commentaire de la LTF, 2009, N. 23 zu Art. 66 BGG; THOMAS GEISER, in: Basler Kommentar, Bundesgerichtsgesetz, 2008, N. 26 ff. zu Art. 66 BGG; HANSJÖRG SEILER, in: Bundesgerichtsgesetz [BGG], 2007, N. 48 zu Art. 66 BGG). Das Bundesgericht kann die Gerichtskosten anders verteilen oder auf die Kostenerhebung verzichten, wenn es die Umstände rechtfertigen (Abs. 1 zweiter Satz). Zudem kann es auf die Erhebung der Gerichtskosten ganz oder teilweise verzichten, wenn ein Fall durch Abstandserklärung oder Vergleich erledigt wird (Abs. 2).

8.1.4 Unter der Herrschaft von Art. 66 Abs. 4 BGG ist, soweit ersichtlich, kein Entscheid ergangen, welcher sich ausdrücklich mit der Kostenpflicht der in personalrechtlichen Streitigkeiten in ihren Vermögensinteressen betroffenen Gemeinden befasst hat. Im Urteil 1C_183/2007 vom 5. Februar 2008 E. 6, nicht publ. in: BGE 134 I 204, in welchem die Höhe des der Beschwerdegegnerin zugesprochenen Entschädigungsanspruchs zur Diskussion stand, hat das Bundesgericht von einer Erhebung von Gerichtskosten zu Lasten einer unterliegenden, Beschwerde führenden öffentlich-rechtlichen Körperschaft abgesehen, ohne dies jedoch näher zu begründen. Es ist indessen kein sachlicher Grund ersichtlich, der es rechtfertigen würde, bezüglich eines als Arbeitgeber in seinen Vermögensinteressen betroffenen Gemeinwesens von der Auferlegung von Gerichtskosten abzusehen (vgl. in diesem Sinne auch SEILER, a.a.O., N. 53 zu Art. 66 BGG). Im vorliegenden Fall haben sich die Beschwerdeführer in einer Sache ans Bundesgericht gewandt, in welcher sie bei Abweisung der Beschwerde dem Beschwerdegegner eine Entschädigung auszurichten haben. Da somit die Voraussetzungen des Ausnahmetatbestandes von Art. 66 Abs. 4 BGG nicht erfüllt sind, haben die unterliegenden Beschwerdeführer die Gerichtskosten unter solidarischer Haftung zu tragen (Art. 66 Abs. 1 und 5 BGG).