Sachverhalt:
A. A._ ist Eigentümer der unüberbauten Parzelle Nr. 1624 in Heiden und der diese erschliessenden Strassenparzelle Nr. 1588 (Sonnenbergstrasse). Die Grundstücke sind Teil der Wohnzone W2a im Gebiet Sonnenberg. Am 9. Juni 2006 stellte A._ bei der Gemeinde Heiden das Begehren, die Sonnenbergstrasse sei in westliche Richtung zu verlängern, und zwar ab dem künftigen Wendeplatz über die benachbarten Grundstücke Nrn. 810 und 1855, die B._ gehören. Der Gemeinderat Heiden lehnte dieses Begehren mit Entscheid vom 24. Oktober 2006 ab. Am 2. Februar 2007 lehnte er in der gleichen Sache auch ein Wiedererwägungsbegehren von A._ ab.
Gegen den Wiedererwägungsentscheid erhob A._ Rekurs beim kantonalen Departement für Bau und Umwelt. Er machte im Wesentlichen geltend, die neue Strassenverbindung sei nötig, weil sonst die künftigen Bewohner der Parzellen-Nrn. 1603, 1604, 1623 und 1624 einen fünf- bis zehnmal längeren Weg in die Langmoosstrasse in Kauf zu nehmen hätten. Durch die direkte Verbindung in die Sonnhalden- und Langmoostrasse könne mancher Fahrkilometer eingespart werden und gleichzeitig könne das östlich davon liegende Quartier (Sonnenberg) vom entsprechenden Durchgangsverkehr entlastet werden. Dies sei aus umweltschutz- und immissionsrechtlichen Gründen sachgerecht, weshalb sich daraus auch die Notwendigkeit dieser Erschliessungsvariante im Sinne von Art. 57 des kantonalen Baugesetzes vom 12. Mai 2003 (BauG/AR, bGS 721.1) ergebe. Das Departement für Bau und Umwelt wies den Rekurs am 9. Juli 2007 ab. Es begründete dies insbesondere damit, dass die im Jahre 1985 vom Regierungsrat mit dem Quartierplan Sonnenberg genehmigte Erschliessung der Parzellen Nrn. 1603, 1604, 1623 und 1624 einzig von der Sonnenbergstrasse her (mit Wendehammer) eine ausreichende Erschliessung darstelle. Damit könne, im Unterschied zur beantragten Verbindung in die Sonnhaldenstrasse, eine übermässige Erschliessung vermieden werden.
Gegen den Rekursentscheid des Departements für Bau und Umwelt gelangte A._ am 13. August 2007 an das Verwaltungsgericht des Kantons Appenzell A.Rh. Er beantragte neben der Aufhebung der vorinstanzlichen Entscheide, der Gemeinderat Heiden sei anzuweisen, die Weiterführung der Sonnenbergstrasse in die Sonnhaldenstrasse in sein Erschliessungsprogramm aufzunehmen und den dafür erforderlichen Flächenbedarf mit den gegebenen planerischen Mitteln sicherzustellen. Nach einem Augenschein wies das Verwaltungsgericht die Beschwerde mit Urteil vom 27. August 2008 ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 13. Mai 2009 beantragt A._ die Aufhebung des Urteils des Verwaltungsgerichts vom 27. August 2008 sowie der unterinstanzlichen Entscheide des Departements für Bau und Umwelt und des Gemeinderats Heiden. Weiter verlangt er, der Gemeinderat sei anzuweisen, die Weiterführung der Sonnenbergstrasse in die Sonnhaldenstrasse in sein Erschliessungsprogramm aufzunehmen und den dafür erforderlichen Flächenbedarf mit den gegebenen planerischen Mitteln sicherzustellen. Er rügt insbesondere eine offensichtlich unrichtige Feststellung des Sachverhalts, die Verletzung von Art. 29 der Kantonsverfassung (SR 131.224.1), die Verletzung von Bundesrecht, namentlich von Art. 1 Abs. 2 lit. a und Art. 3 Abs. 2 lit. c-d und Abs. 3 lit. b RPG (SR 700) sowie der Art. 1 und 11 USG (SR 814.01). Zudem macht er Ermessensmissbrauch und eine Verletzung des Willkürverbots (<ref-law>) geltend.
Das Verwaltungsgericht, das Departement für Bau und Umwelt sowie die Gemeinde Heiden beantragen die Abweisung der Beschwerde. B._ stellt den Antrag, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Der Beschwerdeführer hält in einer weiteren Eingabe an seinen Rechtsbegehren fest.

Erwägungen:
1. 1.1 Das angefochtene Urteil des Verwaltungsgerichts ist ein Entscheid einer letzten kantonalen Instanz (Art. 82 lit. a i.V.m. 86 Abs. 1 lit. d BGG). Ihm liegt ein Beschwerdeverfahren über die Strassenerschliessung von Baugrundstücken und damit eine öffentlich-rechtliche Angelegenheit zugrunde. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung (<ref-ruling> E. 1.2 S. 251, 400 E. 2.1 S. 404). Der Beschwerdeführer ist nach <ref-law> zur Beschwerde berechtigt.
1.2 Gemäss <ref-law> hat die Rechtsschrift die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Die Vorbringen müssen sachbezogen sein, damit aus der Beschwerdeschrift ersichtlich ist, in welchen Punkten und weshalb der angefochtene Entscheid beanstandet wird. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt (<ref-ruling>). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. 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).
1.3 Der Beschwerdeführer bringt in verschiedener Hinsicht vor, die Vorinstanz habe den rechtserheblichen Sachverhalt offensichtlich falsch festgestellt.
Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Soweit die Beschwerdeführer die vorinstanzlichen Sachverhaltsfeststellungen beanstanden und eine mangelhafte Sachverhaltsfeststellung für den Ausgang des Verfahrens entscheidend ist, können sie nur geltend machen, die Feststellungen seien offensichtlich unrichtig oder beruhten auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 97 Abs. 1 und <ref-law>). Eine entsprechende Rüge, ist substanziiert vorzubringen (E. 1.2 hiervor). Vorbehalten bleibt die Sachverhaltsberichtigung von Amtes wegen nach <ref-law> (vgl. <ref-ruling> E. 1.4.3 S. 254 f.).
Die Kritik des Beschwerdeführers an den vorinstanzlichen Sachverhaltsfeststellungen betrifft insbesondere die tatsächlichen Feststellungen zur bau- und planungsrechtlichen Situation des Nachbargrundstücks Nr. 810, das aufgrund einer rechtskräftigen Baubewilligung überbaut wurde und über die Sonnhaldestrasse erschlossen ist. Voraussetzung einer Sachverhaltsrüge ist, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Entsprechend der Substanziierungsobliegenheit von <ref-law> muss der Beschwerdeführer aufzeigen, inwiefern die von ihm behaupteten Mängel bei der Sachverhaltsfeststellung einen Einfluss auf die Beurteilung des Streitgegenstands haben. Dieser prozessualen Obliegenheit kommt der Beschwerdeführer nicht in genügendem Mass nach. Zwar erläutert er einen Zusammenhang zwischen der Erschliessung des Grundstücks Nr. 810 und seiner Parzelle Nr. 1624. Er bestreitet nicht, dass sich das Nachbargrundstück bereits vor der letzten Zonenplanänderung in einer Wohnzone befand und dass es über eine rechtskräftig bewilligte Strassenerschliessung verfügt. Inwiefern die beanstandeten tatsächlichen Feststellungen zur Nachbarparzelle jedoch eine entscheidende Bedeutung bei der rechtlichen Beurteilung der Erschliessung seines eigenen Grundstücks haben könnten, ist nicht ersichtlich. Auf die Sachverhaltsrügen kann somit nicht eingetreten werden. Soweit der Beschwerdeführer im Übrigen die für die Überbauung der Parzelle Nr. 810 erteilte Baubewilligung beanstandet, geht die Beschwerde über den Streitgegenstand hinaus, weshalb insoweit darauf auch nicht eingetreten werden kann.
1.4 Unzulässig ist der Antrag des Beschwerdeführers, auch die unterinstanzlichen Entscheide des Departements für Bau und Umwelt und der Gemeinde Heiden seien aufzuheben. Diese Entscheide sind durch das Urteil des Verwaltungsgerichts ersetzt worden (Devolutiveffekt) und gelten als inhaltlich mitangefochten (<ref-ruling> E. 1.4 S. 144; <ref-ruling> E. 1 S. 441 mit Hinweisen).
1.5 Die übrigen Sachurteilsvoraussetzungen sind erfüllt. Auf die Beschwerde ist somit unter Vorbehalt der Erwägungen 1.2 bis 1.4 hiervor einzutreten.
2. Der Beschwerdeführer bringt im Wesentlichen vor, die Erschliessung seines Grundstücks über die Sonnenbergstrasse nach Osten führe dazu, dass der Weg ins Dorf um rund 600 m verlängert werde. Dies bewirke eine unnötige Umweltbelastung, die mit nur geringem Aufwand mittels einer kurzen Verbindungsstrasse über Parzelle Nr. 810 bis zur Sonnhaldestrasse vermieden werden könne.
2.1 Die Erteilung einer Baubewilligung setzt voraus, dass das Baugrundstück erschlossen ist (Art. 22 Abs. 2 lit. b RPG [SR 700]). Zur Erschliessung gehören alle Einrichtungen, die notwendig sind, damit ein Grundstück zonen- und bauordnungsgerecht genutzt werden kann. Land ist erschlossen, wenn unter anderem eine für die betreffende Nutzung hinreichende Zufahrt besteht (Art. 19 Abs. 1 RPG). Für den Wohnungsbau präzisiert Art. 4 des Wohnbau- und Eigentumsförderungsgesetzes vom 4. Oktober 1974 (WEG, SR 843) den Begriff der Erschliessung. In <ref-law> wird die Erschliessungspflicht geregelt. Diese Bestimmungen ergänzen die allgemeinen Erschliessungsvorschriften gemäss Art. 19 RPG für den Bereich des Wohnungsbaus. Die Erschliessungsanforderungen sind in diesen Vorschriften mit unbestimmten Rechtsbegriffen umschrieben, die nach dem Sinn und Zweck der Bestimmungen und deren Stellung im Gesetz und im Rechtssystem auszulegen sind. Die einzelnen Anforderungen ergeben sich im Detail hauptsächlich erst aus dem kantonalen Recht und der kantonalen Gerichts- und Verwaltungspraxis, die sich am bundesrechtlichen Rahmen zu orientieren haben. Das entsprechende kantonale Recht kann insbesondere das Ausmass der Erschliessungsanlagen und die Anforderungen an die genügende Zugänglichkeit in abstrakter Weise festlegen. Hingegen bleibt es den Kantonen verwehrt, im Rahmen der Konkretisierung der Erschliessungsanforderungen den durch Art. 19 RPG und die Spezialgesetzgebung gezogenen bundesrechtlichen Rahmen zu überschreiten. Kantonales Recht, das Anforderungen stellt, die über eine Konkretisierung hinausgehen, kann indessen nach Massgabe von Art. 22 Abs. 3 RPG zulässig sein (Bernhard Waldmann/Peter Hänni, Raumplanungsgesetz, 2006, N. 13 und 19 zu Art. 19 mit zahlreichen Hinweisen).
Bei der Beurteilung, ob eine Zufahrt ein Baugrundstück hinreichend erschliesst, steht den kantonalen und kommunalen Behörden ein erhebliches Ermessen zu (vgl. <ref-ruling> E. 3a S. 68 mit Hinweisen). Das Bundesgericht überprüft die Auslegung und Anwendung des kantonalen Rechts auf Willkür hin. Willkürlich ist ein Entscheid nicht schon dann, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, sondern erst dann, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Willkür liegt sodann nur vor, wenn nicht bloss die Begründung eines Entscheids, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 5.1 S. 17 f.; <ref-ruling> E. 3.1 S. 473 f.; je mit Hinweisen).
2.2 Das Verwaltungsgericht hält im angefochtenen Entscheid fest, dass die umstrittene Erschliessung im rechtskräftigen Quartierplan festgelegt ist. Es gelangte nach Durchführung eines Augenscheins zum Schluss, dass die vom Beschwerdeführer gewünschte Ringverbindung zu einer übermässigen Erschliessung führen würde. Weder die Parzelle Nr. 1624 noch das Nachbargrundstück Nr. 810 seien auf eine Strassenerschliessung von zwei Seiten her angewiesen. Mit den getrennten Zufahrten seien beide Grundstücke im Sinne von Art. 19 RPG hinreichend erschlossen. Das Verwaltungsgericht anerkannte, dass der Fahrweg von Parzelle Nr. 1624 ins rund 1 km entfernte Dorfzentrum von Heiden ohne Ringstrasse um rund 400 m länger sei. Dies rechtfertige jedoch nicht, dass Motorfahrzeugen immer der kürzest mögliche Weg durch benachbarte Wohngebiete zu öffnen sei. Nach dem geltenden Quartierplan werde der motorisierte Quellverkehr aus dem Wohnquartier namentlich aus Gründen des Lärm- und Fussgängerschutzes in die zweispurig dimensionierte und mit Trottoir ausgestattete Langmoosstrasse (Sammelstrasse) abgeleitet. Weder die Verkehrssicherheit noch die zu erwartende Verkehrsdichte liessen die vom Beschwerdeführer bevorzugte Ringstrassenlösung als zweckmässiger oder gar notwendig erscheinen. Für die Fussgänger habe die vom Beschwerdeführer kritisierte Erschliessung gemäss Quartierplan keine nennenswerte Verlängerung ihres Weges ins Dorfzentrum zur Folge, da der bestehende Fussweg in die Langmoosstrasse in seinem Bestand gesichert sei.
2.3 Der Kritik des Beschwerdeführers an der verwaltungsgerichtlichen Beurteilung der umstrittenen Strassenerschliessung kann nicht gefolgt werden. Die im rechtskräftigen Quartierplan vorgesehene Erschliessung des Grundstücks Nr. 1624 über die Sonnenbergstrasse ist mit dem vom Beschwerdeführer angerufenen Bundesrecht vereinbar. Insbesondere führen die Planungsziele und -grundsätze des RPG und das umweltrechtliche Vorsorgeprinzip zu keiner anderen Lösung. Eine zusätzliche Strassenverbindung über die Parzelle Nr. 810 erscheint bei den gegebenen Verhältnissen im Lichte der Art. 19 RPG und 4 WEG nicht als erforderlich. Das Verwaltungsgericht hat die Recht- und Verhältnismässigkeit der Erschliessung gemäss geltendem Quartierplan geprüft und unter Beachtung des Planungsermessens der kantonalen und kommunalen Behörden mit zutreffender Begründung bejaht. Somit ist auch die Abweisung des Planänderungsbegehrens und der Verzicht auf die Aufnahme der Ringverbindung ins Erschliessungsprogramm nicht zu beanstanden. Von Willkür kann in diesem Zusammenhang keine Rede sein.
3. Es ergibt sich, dass die Beschwerde abzuweisen ist, soweit darauf eingetreten werden kann. Bei diesem Ausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Dieser hat dem anwaltlich vertretenen Beschwerdegegner eine angemessene Parteientschädigung zu bezahlen (<ref-law>). Der Genossenschaft C._ ist im bundesgerichtlichen Verfahren kein Aufwand entstanden, weshalb ihr auch keine Parteientschädigung zusteht (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten werden kann.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat den privaten Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Gemeinderat Heiden, dem Departement Bau und Umwelt des Kantons Appenzell Ausserrhoden und dem Verwaltungsgericht von Appenzell Ausserrhoden, 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 26. August 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Haag