Sachverhalt: A. Am 9. Dezember 1998 beschloss der Regierungsrat des Kantons Zürich, dass bei den Angestellten im Lehrbereich per 1. Juli 1999 Beförderungen vorgenommen werden könnten. Den hierfür vorgesehenen Betrag setzte er auf 0.4 % der Grundbesoldung fest. Mit Schreiben vom 21. Juni 1999 teilte der Prorektor der Zürcher Hochschule Winterthur (ZHW; seit 1. Januar 2008 Zürcher Hochschule für Angewandte Wissenschaften, ZHAW) A._, B._, C._ und D._ sowie weiteren Dozenten mit, dass ihnen im Gegensatz zu anderen Kollegen kein lohnwirksamer Stufenanstieg gewährt werden könne. B. In einem ersten Rechtsmittelverfahren wies das Verwaltungsgericht des Kantons Zürich die Angelegenheit an die ZHW zurück, da der Sachverhalt nicht rechtsgenügend erstellt war. Nachdem die ZHW und die Rekurskommission der Zürcher Hochschulen die Begehren erneut abgewiesen hatten, hiess der Einzelrichter des Verwaltungsgerichts die dagegen gerichtete Beschwerde am 9. Dezember 2005 gut und verpflichtete die ZHW zu Lohnnachzahlungen: A._ sollte nachträglich Fr. 837.-- erhalten, B._, C._ und D._ je Fr. 3'348.--. C. Am 28. März 2006 gelangten die vorgenannten Lehrpersonen an die ZHW mit der Forderung, bei ihnen infolge des Verwaltungsgerichtsentscheids vom 9. Dezember 2005 ab 1. Juli 1999 die gesamte Lohnentwicklung nachzuvollziehen, wie wenn die ZHW damals korrekt gehandelt hätte. Vorab ersuchten sie um die Zustellung anfechtbarer Verfügungen. Nach weiteren Briefwechseln verfügte die ZHW am 22. August 2006 gegenüber A._ und C._ die Lohnnachzahlungen von Fr. 837.-- resp. 3'348.--, unter Abrechnung der Sozialversicherungsbeiträge. Weitergehende Lohnansprüche, Schadenersatzansprüche und Ansprüche auf Verzinsung wies die ZHW ab. D. Zuvor hatte die ZHW C._ am 3. September 2001 per 1. Oktober 2001 neu eingereiht. Die Einreihung erfolgte in die Lohnklasse 23, Jahresstufe 13 des neuen Besoldungssystems. Der Bruttolohn betrug Fr. 157'997.--. E. Das von C._ gegen die Einreihung vom 1. Oktober 2001 angestrengte Rekursverfahren wurde zunächst sistiert und dann durch die Rekurskommission der Zürcher Hochschulen übernommen. Sein Gesuch um Gewährung der unentgeltlichen Rechtspflege wies der Vorsitzende der Rekurskommission ab. Das dagegen angerufene Verwaltungsgericht schützte diesen Entscheid. Im Übrigen wies die Rekurskommission den Rekurs am 9. November 2006 ab, soweit sie darauf eintrat. F. Zuvor rekurrierten A._, B._, C._ und D._ am 2. Oktober 2006 gemeinsam bei der Rekurskommission der Zürcher Hochschulen mit dem Antrag, die Verfügung der ZHW vom 22. August 2006 (lit. C hiervor) aufzuheben und ihnen den Lohn ab 1. Juli 1999 nachzuzahlen. Mit Beschluss vom 7. Juni 2007 trat die Rekurskommission auf die Eingaben von B._ und D._ nicht ein. Die Rekurse von A._ und C._ wies sie ab, soweit sie darauf eintrat. G. Mit Beschwerde vom 5./6. August 2007 beantragten A._, B._, C._ und D._ dem Verwaltungsgericht die Aufhebung der Verfügung der ZHW vom 22. August 2006 und des dazu erlassenen Rekursentscheids vom 7. Juni 2007. Das Urteil des Einzelrichters vom 9. Dezember 2005 sei so zu vollziehen, dass die Beschwerdeführer in finanzieller Hinsicht so gestellt würden, wie wenn sie den individuellen Stufenanstieg per 1. Juli 1999 korrekt erhalten hätten. C._ schliesslich ersuchte um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung (kantonales Verfahren PB.2007.00024). H. Am 10./11. Januar 2007 stellte C._ dem Verwaltungsgericht zudem Antrag auf Aufhebung der mit Anstellungsverfügung vom 3. September 2001 erlassenen Einreihung sowie des Rekursentscheids vom 9. November 2006 (lit. E hiervor, kantonales Verfahren PB.2007.00002). I. Das Verwaltungsgericht des Kantons Zürich vereinigte mit Urteil vom 14. Mai 2008 die beiden Verfahren, wies das Gesuch von C._ um unentgeltliche Rechtspflege und Verbeiständung ab und trat auf die Beschwerden von B._ und D._ nicht ein. Deren Eingaben wurden an die ZHAW (als Rechtsnachfolgerin der ZHW) zur Behandlung weitergeleitet. Weiter verpflichtete das Verwaltungsgericht die ZHAW, A._ auf der geschuldeten Lohnnachzahlung von Fr. 837.-- Zinsen zu 5 % ab 28. März 2001 zu bezahlen. Im Übrigen wies es A._s Beschwerde ab, soweit es darauf eintrat. In Bezug auf C._ wurde die ZHAW mit dem Entscheid verpflichtet, dem Beschwerdeführer auf der geschuldeten Lohnnachzahlung von Fr. 3'348.-- Zinsen zu 5 % ab 28. März 2001 zu bezahlen. Im Übrigen wurden beide Beschwerden C._s abgewiesen, soweit das Verwaltungsgericht darauf eintrat. J. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 5. Juli 2008 wenden sich A._ (Beschwerdeführerin 1), B._ (Beschwerdeführer 2), C._ (Beschwerdeführer 3) und D._ (Beschwerdeführer 4) gegen das Urteil des Zürcher Verwaltungsgerichts vom 14. Mai 2008. Sie stellen auf ca. 17 Seiten 20 Anträge (u.a. Feststellungsbegehren und Ersuchen um Vormerkungen), auf deren Wiedergabe hier verzichtet wird. Im Wesentlichen beantragen sie die Aufhebung des angefochtenen Entscheids, des Beschlusses der Rekurskommission vom 7. Juni 2007 sowie der Verfügungen der ZHAW vom 22. August 2006. Sie fordern zusammengefasst, in finanzieller und versicherungstechnischer Hinsicht so gestellt zu werden, wie wenn sie den lohnwirksamen Stufenanstieg per 1. Juli 1999 korrekt erhalten hätten, wozu die gesamte gesetzlich geregelte Lohnentwicklung rückwirkend nachzuvollziehen sei. Die Zürcher Hochschule für Angewandte Wissenschaften (ZHAW) als Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne, während das Verwaltungsgericht des Kantons Zürich auf eine Vernehmlassung verzichtet. In ihrer Replik halten die Beschwerdeführer sinngemäss an ihren Anträgen fest. 