Sachverhalt:
A. Der Gemeinderat Riehen hat am 26. April 2005 dem Linien- und Erschliessungsplan für den Auhaldenweg zugestimmt. Dieser Weg soll verbreitert und erschlossen werden. Zudem sollen die fehlenden Bau- und Strassenlinien gelegt werden. A.X._ und B.X._, Y._ und Z._ wohnen am Auhaldenweg 12 bzw. an der Schlossstrasse 35 und 37 in Riehen. Sie haben gegen den erwähnten vom 29. April bis 30. Mai 2005 öffentlich aufgelegten Plan Einsprache erhoben, welche vom Gemeinderat Riehen mit Entscheid vom 31. Januar 2007 abgewiesen wurde. Die Einsprecher haben diesen Entscheid des Gemeinderates an den Regierungsrat des Kantons Basel-Stadt weitergezogen. Das Justizdepartement hat den Rekurs dem kantonalen Appellationsgericht als Verwaltungsgericht zum Entscheid überwiesen. Dieses hat ihn mit Urteil vom 16. Mai 2008 abgewiesen.
B. Gegen dieses Urteil des Appellationsgerichts als Verwaltungsgericht führen A.X._ und B.X._, Y._ und Z._ Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie beantragen, das angefochtene Urteil des Appellationsgerichts sei aufzuheben und der Vorinstanz bzw. der Gemeinde Riehen sei zu verbieten, den Auhaldenweg in Riehen im Rahmen einer angeblichen Erschliessung auf 3.60 m (insgesamt 4 m) zu verbreitern. Eventualiter sei das Verfahren an die Vorinstanz zurückzuweisen.
C. Die Einwohnergemeinde Riehen stellt den Antrag, die Beschwerde sei abzuweisen und das angefochtene Urteil sei zu bestätigen. Das Verwaltungsgericht hat in seiner Vernehmlassung darauf verzichtet, einen formellen Antrag zu stellen. In weiteren Stellungnahmen halten die Beschwerdeführer und die Gemeinde Riehen an ihren Rechtsbegehren und Standpunkten fest.

Erwägungen:
1. Das Bundesgericht prüft seine Zuständigkeit und die Zulässigkeit der Beschwerde von Amtes wegen (<ref-law>; <ref-ruling> E. 1.1 S. 251).
1.1 Angefochten ist ein kantonal letztinstanzlicher Entscheid, mit dem eine Beschwerde gegen einen Linien- und Erschliessungsplan im Sinne der §§ 96 ff. des Bau- und Planungsgesetzes des Kantons Basel-Stadt vom 17. November 1999 (BPG/BS, SG 730.100) und damit einen (Sonder-)Nutzungsplan im Sinne von Art. 14 ff. RPG (SR 700) abgewiesen wurde. Dagegen steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (<ref-law>).
1.2 Die erforderliche Genehmigung des strittigen Baulinienplans durch die zuständige kantonale Behörde (Art. 26 RPG; §§ 114 f. BPG/BS) liegt nicht vor. Das Bundesgericht tritt auf Beschwerden gegen Rechtsmittelentscheide über die Festsetzung von Nutzungsplänen grundsätzlich nur ein, wenn ein Genehmigungsentscheid im Sinne von Art. 26 Abs. 1 RPG vorliegt (vgl. Urteile des Bundesgerichts 1C_190/2007 vom 7. Dezember 2007 E. 2.2; 1C_39/2008 vom 28. August 2008 E. 1.1.1; 1C_212/2008 vom 17. November 2008 E. 2.2, je mit Hinweisen).
Die Koordinationsgrundsätze gemäss Art. 25a RPG erfordern eine Abstimmung des Rechtsmittel- und des Genehmigungsentscheids (Urteil des Bundesgerichts 1C_190/2007 vom 7. Dezember 2007 E. 2.2.2.2 mit Hinweisen). Bundesrechtlich vorgeschrieben ist eine zweifache Überprüfungsmöglichkeit von (kommunalen) Nutzungsplänen: Einerseits unterliegen diese der Genehmigung durch eine kantonale Behörde (Art. 26 RPG). Andererseits müssen sie mit einem Rechtsmittel angefochten werden können (Art. 33 RPG). Genehmigung und Anfechtung haben unterschiedliche Funktionen: Die Genehmigung muss von Amtes wegen eingeholt werden. Sie ist eine gesamtheitliche Beurteilung der Planung auf ihre Übereinstimmung mit übergeordnetem Recht sowie mit der Richtplanung. Der Genehmigungsentscheid stellt jedoch nur eine vorläufige Kontrolle dar, an welche die Rechtsmittelbehörde nicht gebunden ist. Ein Anfechtungsverfahren findet hingegen nur statt, wenn jemand ein Rechtsmittel ergreift. Es ist häufig punktuell: Die Beschwerdeführer können sich auf die Anfechtung bestimmter, für sie wesentlicher Punkte beschränken. Der Verfahrensgegenstand im Rechtsmittelverfahren wird durch die Anträge der Beschwerdeführer bestimmt und ist möglicherweise eingeschränkt. Der Rechtsmittelentscheid beschränkt sich dann ebenfalls auf die angefochtenen Punkte (Urteil des Bundesgerichts 1P.222/2000 vom 22. November 2000, in: ZBl 102/2001 S. 383 ff. E. 3e mit Hinweisen). Sind die Genehmigungsvoraussetzungen hingegen nicht erfüllt, wird der Nutzungsplan mangels Genehmigung nicht rechtsverbindlich (Art. 26 Abs. 3 RPG e contrario). Je nach Ausgestaltung des kantonalen Rechts kann der zuständigen Behörde die Kompetenz zukommen, bei einer Nichtgenehmigung bis zur Korrektur des Plans durch die planfestsetzende Behörde vorsorgliche Massnahmen zu erlassen. Wo nur einzelne, klar bestimmbare Planinhalte nicht genehmigt werden können, kann auch eine teilweise Nichtgenehmigung in Frage kommen. Voraussetzung dazu ist, dass die genehmigten und die nicht genehmigten Vorschriften von einander sachlich unabhängig sind (vgl. BERNHARD WALDMANN/PETER HÄNNI, Raumplanungsgesetz, 2006, Art. 26 Rz. 10 f. mit Hinweisen).
Auf welche Weise die Koordination zwischen dem Genehmigungs- und dem Rechtsmittelentscheid hergestellt wird, bleibt grundsätzlich den Kantonen überlassen (Art. 25 Abs. 1 RPG; Urteil des Bundesgerichts 1P.222/2000 vom 22. November 2000, in: ZBl 102/2001 S. 383 ff. E. 3c mit Hinweisen). Der Genehmigungsentscheid muss jedoch spätestens im Rahmen des Verfahrens vor der letzten kantonalen Rechtsmittelinstanz eingeholt werden; die gebotene Koordination kann nicht erst vor Bundesgericht erfolgen (Urteil des Bundesgerichts 1C_190/2007 vom 7. Dezember 2007 E. 2.2.2.2 und 2.2.3 mit Hinweisen).
1.3 Zonen-, Linien- und Bebauungspläne der Landgemeinden sind gemäss § 114 Abs. 1 BPG/BS dem für die Raumplanung zuständigen Departement zur Genehmigung zu unterbreiten. Sie werden von der Genehmigungsbehörde auf Rechtmässigkeit, Zweckmässigkeit und Angemessenheit überprüft (§ 114 Abs. 2 BPG/BS). Die Genehmigung hat rechtsbegründende Wirkung (Art. 26 Abs. 3 RPG). Im Unterschied zu den Rechtsmittelinstanzen, welche sich auf umstrittene Teile des bei ihnen angefochtenen Nutzungsplans zu konzentrieren haben, erfolgt im kantonalen Genehmigungsverfahren eine ganzheitliche Überprüfung des gesamten zu genehmigenden Plans. Mit Entscheiden, die das Bundesgericht vor der kantonalen Plangenehmigung über einzelne umstrittene Teile des Nutzungsplans fällen würde, käme es in der Regel zu einem unzulässigen Eingriff in die von grosser Autonomie geprägte Aufgabe der kantonalen Genehmigungs- und Rechtsmittelbehörden (vgl. <ref-law>). Von Ausnahmen abgesehen, darf daher das Bundesgericht einen Rechtsmittelentscheid über einen Nutzungsplan nur beurteilen, wenn der Genehmigungsentscheid im Rechtsmittelverfahren spätestens bei der letzten kantonalen Instanz vorlag, so dass sie diesen unter Wahrung des Anspruchs auf rechtliches Gehör (<ref-law>) in die Beurteilung einbeziehen konnte. Eine Ausnahme wurde bei einem mit Rechtsverweigerungsbeschwerde angefochtenen letztinstanzlichen kantonalen Nichteintretensentscheid angenommen (Urteil des Bundesgerichts 1C_39/2008 vom 28. August 2008 E. 1.2). Eine solche Ausnahme ist im vorliegenden Fall nicht gegeben.
Den Kantonen obliegt es zu bestimmen, in welchem Zeitpunkt des Rechtsschutzverfahrens der Genehmigungsentscheid über den Nutzungsplan ins Rechtsschutzverfahren einzubeziehen ist. Das basel-städtische Recht sieht vor, dass über die Genehmigung auch entschieden werden kann, wenn Rekurse gegen die Planfestsetzung hängig sind (§ 114 Abs. 3 BPG/BS). Spätestens muss der Genehmigungsentscheid wie erwähnt während dem Verfahren vor der letzten kantonalen Instanz ergehen und berücksichtigt werden. So veranlasst beispielsweise das Verwaltungsgericht des Kantons Zürich vor der Behandlung von Beschwerden gegen "Entscheide über Bau- und Zonenordnungen, Sonderbauvorschriften, Gestaltungspläne oder Erschliessungspläne" die Baudirektion, für den Genehmigungsentscheid zu sorgen (§ 329 Abs. 4 des Zürcher Planungs- und Baugesetzes vom 7. September 1975 [PBG/ZH]; vgl. Urteile 1C_212/2008 vom 17. November 2008 E. 2.4 und 1P.222/2000 vom 22. November 2000, in: ZBl 102/2001 S. 383 ff. E. 3c mit Hinweisen).
2. Aus den vorstehenden Erwägungen ergibt sich, dass auf die vorliegende Beschwerde nicht eingetreten werden kann, weil die für die Verbindlichkeit eines Nutzungsplans erforderliche Genehmigung im Sinne von Art. 26 Abs. 3 RPG und §§ 114 f. BPG/BS fehlt. Damit liegt noch kein letztinstanzlicher kantonaler Endentscheid über die Nutzungsplanung vor, welcher die Rechte und Pflichten der betroffenen Personen verbindlich regelt. Das Bundesgericht tritt auf Beschwerden gegen Nutzungsplaninhalte grundsätzlich nur ein, wenn die erforderliche kantonale Genehmigung vorliegt. Dass dies mitunter dazu führen kann, dass genehmigte Nutzungspläne auf Grund von späteren Rechtsmittelentscheiden im Rahmen eines weiteren Planfestsetzungsverfahrens wieder geändert werden müssen, vermag an dieser Beurteilung nichts zu ändern.
Den Beschwerdeführern ist im weiteren kantonalen Verfahren Gelegenheit zu geben, den Genehmigungsentscheid nach dessen Vorliegen sachgerecht anzufechten, soweit sie dadurch beschwert sind. Es obliegt den zuständigen kantonalen Instanzen, die erforderliche Koordination sicherzustellen.
3. Unter Berücksichtigung der Umstände der vorliegenden Angelegenheit erscheint es gerechtfertigt, auf die Erhebung von Gerichtskosten zu verzichten (<ref-law>). Es ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Es werden keine Gerichtskosten erhoben.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Einwohnergemeinde Riehen und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht schriftlich mitgeteilt.
Lausanne, 5. Dezember 2008
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Haag