Sachverhalt:
A. X._ war ab dem Schuljahr 1994/1995 bis zu seiner Pensionierung am 31. Juli 2007 als Lehrer mit Teilzeitpensum an der Integrationsschule (heute Integrations-Brückenangebot, IBA, genannt) tätig. Neben dem IBA, welches zur Eingliederung von schweizerischen und ausländischen fremdsprachigen Jugendlichen im Alter von 16 bis 19 Jahren geschaffen worden war, existieren im Kanton Zug zwei weitere "Brückenangebote": das schulische Brückenangebot (SBA, vormals Berufsvorbereitungsschule genannt) und das kombinierte Brückenangebot (KBA, vormals BVL-Extra genannt). Das IBA wurde bis Ende des Schuljahres 2007/2008 im Auftrag der Direktion für Bildung und Kultur von den Stadtschulen Zug geführt. Arbeitgeberin der dort angestellten Lehrpersonen ist die Stadt Zug.
Mit Beschlüssen vom 28. Juni 2005, 16. August 2005 und 8. November 2005 reduzierte der Regierungsrat des Kantons Zug die Anzahl wöchentlicher Pflichtlektionen für Lehrpersonen des IBA von 28 auf 26. Damit führte er mit Wirkung ab 1. August 2006 die gleiche Regelung wie bei den beiden anderen Brückenangeboten ein, wo die Anzahl wöchentlicher Pflichtlektionen bereits vorher 26 betragen hatte. Der Regierungsrat sah sich zu diesem Schritt veranlasst, nachdem der Schlussbericht der "Projektgruppe zur Überarbeitung des Konzepts für das Integrationsbrückenangebot" gezeigt hatte, dass Arbeit und Belastung der Lehrpersonen am IBA mit jener am SBA und am KBA absolut vergleichbar seien.
Mit Eingabe vom 11. Juli 2006 erhob X._ Verwaltungsbeschwerde. Er beantragte unter anderem, seine 26 Pflichtlektionen überschreitende Mehrleistung sei abzugelten. Infolge Beschwerderückzugs schrieb die Sicherheitsdirektion des Kantons Zug die Beschwerde mit Verfügung vom 6. Dezember 2006 als erledigt ab.
Eine entsprechende, mit Schreiben vom 21. Oktober 2006 geltend gemachte Forderung nach rückwirkender Abgeltung der zuviel geleisteten Unterrichtsstunden wies der Stadtrat von Zug mit Verfügung vom 14. November 2006 ab. X._ erhob gegen diese Verfügung Beschwerde beim Regierungsrat. Mit Beschluss vom 6. November 2007 wies der Regierungsrat das Rechtsmittel ab. Eine gegen diesen Beschluss gerichtete Beschwerde wurde vom Verwaltungsgericht des Kantons Zug mit Urteil vom 31. Oktober 2008 ebenfalls abgewiesen.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 17. Dezember 2008 beantragt X._, das Urteil des Verwaltungsgerichts sei aufzuheben und es sei rückwirkend für den Zeitraum von 2000 bis 2006 Rechtsgleichheit herzustellen. Er rügt eine Verletzung von Art. 8 Abs. 1 und 3 BV sowie sinngemäss eine willkürliche Anwendung von § 39 des Personalgesetzes des Kantons Zug vom 1. September 1994 (BGS 154.21).
Der Regierungsrat beantragt in seiner Vernehmlassung die Abweisung der Beschwerde. Der Stadtrat und das Verwaltungsgericht schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1. Der angefochtene Entscheid betrifft die Nachzahlung von Lohn aus einem öffentlich-rechtlichen Anstellungsverhältnis, mithin eine öffentlich-rechtliche Angelegenheit (<ref-law>). Neben der Aufhebung des vorinstanzlichen Entscheids beantragt der Beschwerdeführer, es sei rückwirkend für den Zeitraum zwischen den Jahren 2000 und 2006 Rechtsgleichheit herzustellen. Aus der Beschwerdebegründung geht hervor, dass er mit diesem Begehren eine Forderung in der Höhe von Fr. 30'014.-- geltend machen will (vgl. dazu <ref-ruling> E. 1.4 S. 414 f. mit Hinweisen). Es handelt sich somit um eine vermögensrechtliche Angelegenheit, und der Ausschlussgrund von <ref-law> ist nicht gegeben. Der Streitwert überschreitet die von <ref-law> festgelegte Mindesthöhe von Fr. 15'000.--. Der Beschwerdeführer hat am vorinstanzlichen Verfahren teilgenommen. Er ist als Adressat des angefochtenen Entscheids besonders berührt und hat ein schutzwürdiges Interesse an dessen Aufhebung bzw. Änderung (<ref-law>).
Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Unter dem Vorbehalt hinreichend begründeter Rügen (Art. 42 Abs. 2 und 106 Abs. 2 BGG) ist auf die Beschwerde einzutreten.
2. 2.1 Der Beschwerdeführer rügt eine Verletzung des Gleichbehandlungsgebots von <ref-law> und des Anspruchs von Mann und Frau auf gleichen Lohn für gleichwertige Arbeit nach <ref-law>.
2.2 Inwiefern die für den Beschwerdeführer bis zum 1. August 2006 geltende Besoldungsordnung eine geschlechtsspezifische, direkte oder indirekte Diskriminierung bedeuten sollte, wird in der Beschwerdeschrift nicht dargelegt. Auf die Rüge der Verletzung von <ref-law> ist nicht einzutreten (<ref-law>).
2.3 In Bezug auf das vom Beschwerdeführer ebenfalls angerufene Gleichbehandlungsgebot von <ref-law> ist der sich von <ref-law> unterscheidende Gehalt zu beachten. Der Anspruch auf gleiche Entlöhnung von Mann und Frau ist in <ref-law> als subjektives Individualrecht ausgestaltet. Bei Nachweis einer ungerechtfertigten Diskriminierung besteht ein direkter Anspruch auf einen diskriminierungsfreien Lohn, der im Rahmen der bundesrechtlichen Verjährungsregeln auch rückwirkend geltend gemacht werden kann. Bei ungleichen Besoldungen, die nicht geschlechtsspezifisch bedingt sind, liegen die Dinge anders: Hier gilt als Schranke lediglich das allgemeine Rechtsgleichheitsgebot von <ref-law>, welches nicht unmittelbar ein subjektives Recht auf einen rechtsgleichen Lohn verschafft. Von Verfassungs wegen kann vielmehr lediglich verlangt werden, dass der rechtsungleiche Zustand auf geeignete Weise und in angemessener Frist behoben wird. Was die Angemessenheit der Frist anbelangt, so darf in vertretbarer Weise berücksichtigt werden, wann sich ein Betroffener erstmals gegen die beanstandete Rechtsungleichheit gewehrt hat. Es ist nicht unhaltbar, einen rechtsungleichen Zustand erst mit Wirkung ab jenem Zeitpunkt zu korrigieren, in dem durch den Betroffenen ein entsprechendes Begehren gestellt worden ist (<ref-ruling> E. 3.6 f. S. 109 f. mit Hinweis; Urteil 2P.287/2005 vom 12. April 2006 E. 2.3). Nicht von Bedeutung ist, ob die zuständigen Behörden bereits vorher um den rechtsungleichen Zustand wussten oder diesen bei der Anwendung der gebotenen Sorgfalt hätten kennen müssen.
Nach den insoweit unbestrittenen Feststellungen der Vorinstanz hat der Beschwerdeführer erstmals mit seiner Beschwerde vom 11. Juli 2006 geltend gemacht, sein Anspruch auf rechtsgleichen Lohn sei infolge einer im Vergleich zu den Lehrpersonen der anderen Brückenangebote höheren Zahl von Pflichtlektionen verletzt worden. Dies geschah unmittelbar vor der Reduktion der wöchentlichen Pflichtlektionen bei den Lehrpersonen des Integrations-Brückenangebots (IBA) am 1. August 2006. Unter diesen Voraussetzungen kann nicht gesagt werden, dass der angeblich rechtsungleiche Zustand nicht innert angemessener Frist beseitigt worden wäre.
Die Rüge des Beschwerdeführers erweist sich damit als unbegründet und es kann offen bleiben, ob die vor dem 1. August 2006 geltende Regelung tatsächlich rechtsungleich war. Lediglich der Vollständigkeit halber sei darauf hingewiesen, dass das Bundesgericht in seiner Rechtsprechung stets betont hat, den Behörden komme bei der Auswahl der für die Besoldung des Personals massgebenden Kriterien ein weiter Ermessensspielraum zu (vgl. im Einzelnen <ref-ruling> E. 3.1 S. 107 mit Hinweisen). Der blosse Umstand, dass der Regierungsrat des Kantons Zug die Anzahl der Pflichtlektionen änderte und diesen Schritt mit dem Rechtsgleichheitsgebot begründete, bedeutet nicht a priori, dass die bisherige Regelung <ref-law> verletzte.
3. 3.1 Der Beschwerdeführer rügt schliesslich sinngemäss eine willkürliche Anwendung von § 39 des kantonalen Personalgesetzes. Nach dieser Bestimmung haben Mitarbeiterinnen und Mitarbeiter bei vergleichbarer Ausbildung und Erfahrung, soweit sie für die Arbeit von Nutzen sind, Anspruch auf gleichen Lohn für gleichwertige Arbeit und Leistung.
3.2 Der Beschwerdeführer stand in einem Arbeitsverhältnis zur Einwohnergemeinde Zug, sodass in erster Linie deren Personalreglement vom 5. September 2000 (SRZ 171.1) zur Anwendung kommt (§ 1 Personalreglement). In Bezug auf das für Lehrpersonen geltende Recht bestimmen § 51 Abs. 1 und § 52 Abs. 1 Personalreglement, dass das Arbeitsverhältnis zwischen der Lehrerschaft und der Einwohnergemeinde Zug sich nach dem kantonalen Lehrerbesoldungsgesetz und dem kantonalen Personalgesetz richtet. Der vom Beschwerdeführer angerufene § 39 Personalgesetz ist somit anwendbar. Diese kantonalrechtliche Bestimmung ist im Übrigen weitgehend identisch mit § 19 der kommunalen Personalverordnung vom 24. Oktober 2000 (SRZ 171.11). Der einzige Unterschied besteht darin, dass § 19 Personalverordnung von "Mitarbeitenden" spricht, § 39 Personalgesetz dagegen wie gesehen von "Mitarbeiterinnen und Mitarbeitern".
3.3 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung 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. 2.1 S. 211; <ref-ruling> E. 3.1 S. 473 f.; je mit Hinweisen).
Hinsichtlich der dem Beschwerdeführer in diesem Zusammenhang obliegenden Begründungsanforderungen gilt <ref-law>. Danach überprüft das Bundesgericht die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht) nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist. Es prüft mit anderen Worten nur klar und detailliert erhobene und, soweit möglich, belegte Rügen. Auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein. Wird eine Verletzung des Willkürverbots geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen dargelegt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.1 und 2.2 S. 245 f. mit Hinweisen).
3.4 Das Verwaltungsgericht führt aus, die erwähnten kantonalen und kommunalen Rechtsnormen räumten keine über <ref-law> hinausreichenden Ansprüche ein. Wohl könnte man sich die Frage stellen, ob gemäss § 39 des kantonalen Personalgesetzes oder zumindest gemäss § 19 der kommunalen Personalverordnung mit seiner geschlechtsneutralen Formulierung der Lohngleichheitsanspruch als subjektives Individualrecht nicht geschlechtsspezifisch zu verstehen sei. Massgebend ist indessen ausschliesslich, ob die Auslegung durch das Verwaltungsgericht willkürlich ist. Der Beschwerdeführer legt in keiner Weise dar, weshalb dies zutreffen sollte. Auf seine Rüge ist deshalb nicht einzutreten.
4. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf einzutreten ist. Diesem Ausgang des Verfahrens entsprechend sind die Gerichtskosten dem unterliegenden Beschwerdeführer aufzuerlegen (<ref-law>). Der Einwohnergemeinde Zug, die in ihrem amtlichen Wirkungskreis obsiegt hat, ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird dem Beschwerdeführer, der Einwohnergemeinde Zug sowie dem Regierungsrat und dem Verwaltungsgericht des Kantons Zug, Verwaltungsrechtliche Kammer, schriftlich mitgeteilt.
Lausanne, 14. Mai 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold