Sachverhalt:
A. Am 4. April 2006 genehmigte der Regierungsrat des Kantons Solothurn den Teilzonen- und Gestaltungsplan "Fegetzhof" mit Sonderbauvorschriften. Am 25. August 2008 reichten die Eheleute Y._ ein Gesuch für den Bau eines Einfamilienhauses auf der im Eigentum des Kantons Solothurn stehenden und im Planperimeter liegenden Parzelle Nr. 6780 ein. Gegen das Baugesuch erhoben die Eheleute X._ sowie die Eheleute Z._ Einsprache. Mit Beschluss vom 25. November 2008 wies die Baukommission der Stadt Solothurn die Einsprachen ab und erteilte die Baubewilligung.
Dagegen erhoben die Eheleute X._ beim Verwaltungsgericht des Kantons Solothurn Beschwerde. Gleichzeitig fochten sie einen zweiten Entscheid der Baukommission an, mit welchem diese das Baugesuch eines weiteren Gesuchstellers für die benachbarte Parzelle Nr. 6564 gutgeheissen hatte. Mit Urteil vom 16. Juni 2009 hiess das Verwaltungsgericht diese zweite Beschwerde gut und wies die Angelegenheit zu neuem Entscheid an die Baukommission zurück. Die Beschwerde gegen das Baugesuch der Eheleute Y._ wies es dagegen ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 25. August 2009 beantragen die Eheleute X._, das Urteil des Verwaltungsgerichts vom 16. Juni 2009 sei, insoweit es das Baugesuch der Eheleute Y._ betreffe, aufzuheben und die Sache sei zur neuen Entscheidung an das Verwaltungsgericht, eventualiter an die Baukommission zurückzuweisen. In verfahrensrechtlicher Hinsicht beantragen sie, es sei im Verfahren vor Bundesgericht ein Augenschein durchzuführen und der Beschwerde sei die aufschiebende Wirkung zuzuerkennen.
Das Verwaltungsgericht, die Baukommission, der Kanton Solothurn sowie die Eheleute Y._ beantragen in ihrer jeweiligen Vernehmlassung die Abweisung der Beschwerde, soweit darauf einzutreten sei. In ihrer Stellungnahme dazu halten die Beschwerdeführer im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest. Mit Präsidialverfügung vom 18. September 2009 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Dem angefochtenen Entscheid liegt ein Beschwerdeverfahren über eine baurechtliche Bewilligung zu Grunde. Nach Art. 34 Abs. 1 RPG (SR 700) gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält keinen Ausschlussgrund (<ref-law>). Angefochten ist ein Entscheid einer letzten kantonalen Instanz, welcher in Bezug auf das vorliegend umstrittene Baugesuch das Verfahren abschliesst (Art. 86 Abs. 1 lit. d, Art. 90 BGG). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen, sind als Nachbarn durch den angefochtenen Entscheid besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (<ref-law>). Unter dem Vorbehalt der nachfolgenden Erwägungen ist auf die Beschwerde einzutreten.
1.2 Die Beschwerdeführer rügen eine offensichtlich unrichtige Feststellung des Sachverhalts durch die Vorinstanz. Diese habe das Gewässer auf dem Gestaltungsplanareal zu Unrecht nicht als Bach bezeichnet, sondern festgehalten, es könne "erst ungefähr ab Höhe Baufeld C2" von einem Bach gesprochen werden.
Gemäss <ref-law> kann die Feststellung des Sachverhalts nur gerügt werden, wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann. Wie aus den nachfolgenden Erwägungen ersichtlich, ist vorliegend der Verfahrensausgang nicht von der Qualifizierung des umstrittenen Gewässers abhängig. Auf die Rüge ist deshalb nicht einzutreten.
1.3 In der Replik vom 9. November 2009 machen die Beschwerdeführer neue Ausführungen zum Sachverhalt und offerieren neue Beweismittel, die in der Beschwerdeschrift nicht vorgebracht wurden. Insbesondere bestreiten sie neu die Feststellung der Vorinstanz, wonach es bei dem Gewässer wegen seiner geringen Grösse keinen erkennbaren Uferbereich mit einer Verlandungszone gebe und die bestehenden Pflanzen deshalb nicht eigentlich das Ufer bedeckten, sondern sich lediglich an dieses anschliessen würden. Nach der Rechtsprechung des Bundesgerichts ist eine Beschwerdeergänzung jedoch nach Ablauf der Beschwerdefrist, auf dem Weg der Replik nur insoweit statthaft, als die Ausführungen in der Vernehmlassung eines anderen Verfahrensbeteiligten dazu Anlass geben (vgl. <ref-ruling> E. 2.2 S. 21 mit Hinweisen). Diese Voraussetzung ist vorliegend nicht erfüllt, sodass auf die genannten Vorbringen nicht einzutreten ist.
1.4 Der rechtserhebliche Sachverhalt geht aus den Akten hinreichend hervor. Auf die Durchführung eines Augenscheins kann daher verzichtet werden.
2. 2.1 Die Beschwerdeführer rügen eine Verletzung des Bundesgesetzes vom 24. Januar 1991 über den Schutz der Gewässer (GSchG; SR 814.20). Das Vorgehen der kantonalen Behörden laufe der in <ref-law> formulierten Zwecksetzung zuwider, wonach mit dem Gesetz die Erhaltung der Gewässer als Landschaftselemente angestrebt werde. Auch würden Art. 3 und Art. 37 Abs. 1 lit. a und Abs. 2 lit. c GSchG missachtet, weil das Bauvorhaben mit der Beseitigung von Ufervegetation verbunden sei.
2.2 Gemäss <ref-law> ist jedermann verpflichtet, alle nach den Umständen gebotene Sorgfalt anzuwenden, um nachteilige Einwirkungen auf die Gewässer zu vermeiden. Die Bestimmung verlangt, dass alles Zumutbare unternommen wird, um eine Gewässerverschmutzung zu verhindern (Urteil 1C_390/2008 vom 15. Juni 2009 E. 2.1 mit Hinweis, in: URP 2009 S. 634). Eine in diesem Sinne nachteilige Einwirkung auf ein Gewässer wird nicht geltend gemacht und ist auch nicht erkennbar.
<ref-law> stellt Voraussetzungen für die Verbauung und Korrektion von Fliessgewässern auf. Im Einklang mit dem allgemeinen Sprachgebrauch sind gemäss der Botschaft vom 29. April 1987 zur Volksinitiative "zur Rettung unserer Gewässer" und zur Revision des Bundesgesetzes über den Schutz der Gewässer unter Verbauungen und Korrektionen Eingriffe zu verstehen, die eine Stabilisierung, Veränderung oder Verlegung des Gewässers bewirken. Punktuelle Massnahmen für Bauten an oder in Gewässern, mit denen nicht die Stabilisierung eines Gewässerbetts bezweckt wird, fallen dagegen nicht darunter (BBl 1987 II 1141 Ziff. 322.3; vgl. auch Urteil 1A.62/1998 vom 15. Dezember 1998 E. 3 mit Hinweis, in: ZBl 101/2000 S. 323). Die von den Beschwerdeführern geltend gemachte Beseitigung von Ufervegetation stellt somit keine Verbauung oder Korrektion eines Fliessgewässers im Sinne von <ref-law> dar.
Auch eine Auslegung von Art. 3 und <ref-law> im Lichte der Zweckbestimmung von <ref-law> führt zu keinem anderen Schluss. Die Rüge der Verletzung des Gewässerschutzgesetzes erweist sich deshalb als unbegründet.
3. 3.1 Die Beschwerdeführer argumentieren weiter, der angefochtene Entscheid verletze Art. 21 Abs. 1 des Bundesgesetzes vom 1. Juli 1966 über den Natur- und Heimatschutz (NHG; SR 451). Gemäss dieser Bestimmung darf die Ufervegetation (Schilf- und Binsenbestände, Auenvegetationen sowie andere natürliche Pflanzengesellschaften im Uferbereich) weder gerodet noch überschüttet noch auf andere Weise zum Absterben gebracht werden.
3.2 Als Ufervegetation im Sinne dieser Bestimmung gelten natürliche Pflanzengesellschaften im Uferbereich. Dazu gehören Pflanzen, welche die Ufer bedecken oder im Wasser wachsen. Der Uferbereich erstreckt sich neben dem eigentlichen Ufer auch auf die Verlandungszone, soweit sich diese im Schwankungsbereich des Spiegels des fraglichen Gewässers befindet. Dabei dürfen auch hohe Wasserstände berücksichtigt werden, wie sie in gewissen Abständen vorkommen. Hingegen sind aussergewöhnliche, nur ganz selten auftretende Hochwasserstände ausser Acht zu lassen. Nicht zur Ufervegetation zählen ausserhalb des umschriebenen Uferbereichs wachsende Pflanzen, auch wenn sie für Feuchtgebiete typisch sind. <ref-law> schützt somit die für den Uferbereich typischen Pflanzen (<ref-ruling> E. 3a S. 118 f.; Urteil 1A.183/2001 vom 18. September 2002 E. 8.2.1; je mit Hinweisen).
Die Vorinstanz führte aus, vom Retentionsbecken bis zum Baubereich C2 sei kein Bachbett erkennbar. Es handle sich lediglich um ein kleines Rinnsal, welches bei genügend hohem Gras kaum noch zu sehen sei. Bereits bei kürzeren Trockenperioden führe es kaum Wasser. Dies sei auch am Augenschein so gewesen. Das Wurzelwerk der vorhandenen Pflanzen bildeten mit dem Rinnsal keine Einheit, sodass nicht von Ufergehölz gesprochen werden könne.
Die Beschwerdeführer sind zwar der Ansicht, dass es sich bei dem Gewässer auch im Bereich des Bauprojekts um einen Bach und nicht lediglich ein Rinnsal handle und bezeichnen die Ausführungen des Verwaltungsgerichts als nicht überzeugend. Sie bestreiteten jedoch die Darstellung der Vorinstanz nicht (bzw. nicht rechtzeitig, vgl. E. 1.3 hiervor), wonach es bei dem Gewässer wegen seiner geringen Grösse keinen erkennbaren Uferbereich mit einer Verlandungszone gebe und die bestehenden Pflanzen deshalb nicht eigentlich das Ufer bedeckten, sondern sich lediglich an dieses anschliessen würden. Darauf kommt es jedoch nach dem Gesagten an. Die Rüge der Beschwerdeführer erweist sich deshalb als unbegründet.
4. 4.1 Die Beschwerdeführer machen eine willkürliche Anwendung von § 31 der Verordnung des Kantons Solothurn vom 14. November 1980 über den Natur- und Heimatschutz (BGS 435.141; im Folgenden: NHV/SO) geltend. Danach werden sämtliche Bäche, Flüsse und Seen und deren Ufer durch die nachfolgenden Bestimmungen und durch Richt- und Nutzungspläne unter Schutz gestellt. Die Beschwerdeführer verweisen diesbezüglich auf <ref-law>/SO, welcher folgenden Wortlaut hat:
Der Bauabstand für Bauten und bauliche Anlagen zu den Gewässern innerhalb der Bauzone ist durch Baulinien oder Uferschutzzonen vorgegeben. Sofern solche fehlen, beträgt der Bauabstand innerhalb der Bauzone entlang von Bächen 4 m, entlang von Flüssen und Seen 10 m.
Die Beschwerdeführer räumen ein, dass der Gestaltungsplan Fegetzhof Baulinien aufweist. Diese stünden jedoch insofern im Widerspruch zu § 11 der Sonderbauvorschriften (im Folgenden: SBV), als sie den von dieser Bestimmung festgelegten Gewässerabstand von 5 m unterschritten. Dieser Widerspruch zwischen den Sonderbauvorschriften und dem Gestaltungsplan verletze das Willkürverbot (<ref-law>). Zudem verstosse es gegen den Grundsatz von Treu und Glauben, wenn die Bedeutung von § 11 SBV "herabgemindert" werde, nachdem der Schutz des Gewässers und des Pflanzenbestands bei der Ausarbeitung des Gestaltungsplans noch betont worden sei. Die betroffenen Grundeigentümer hätten damals wegen entsprechender Zusicherungen davon abgesehen, Einsprache zu erheben.
Unter dem Titel "Umgebung/Grünbereiche" sieht § 11 Abs. 2 SBV Folgendes vor:
Die Ufer der Gewässer (Bach) sind in einem Bereich/Abstand von 5 m naturnah zu gestalten und zu nutzen ... Nicht zulässig sind das Lagern von Material aller Art, insbesondere Kompostgitter und Kompostbehälter, das Errichten von Zäunen, Gartenanlagen und Erholungseinrichtungen. In diesem Bereich dürfen auch keine Dünger und Pflanzenbehandlungsmittel eingesetzt werden.
4.2 Die Vorinstanz legte dar, § 11 SBV gelte ausschliesslich für die Umgebung und den Grünbereich (im Gestaltungsplan grün gefärbt). § 5 SBV regle dagegen den Baubereich B1 und C1 (im Gestaltungsplan orange gefärbt). Diese Abgrenzung habe zur Folge, dass der in § 11 SBV festgelegte Gewässerabstand nur dort gelte, wo die Breite des Grünbereichs einen solchen Abstand zulasse. Planerisch sei diese Lösung zwar unbefriedigend, doch ergäben auf diese Weise der Gestaltungsplan und die Sonderbauvorschriften einen eindeutigen Sinn.
4.3 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung dann 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. 4.1 S. 133 mit Hinweisen).
Die Auslegung des Verwaltungsgerichts lässt keine Willkür im eben umschriebenen Sinn erkennen. Vielmehr bringt sie den Gestaltungsplan, welcher im strittigen Bereich einen Grünstreifen von lediglich 3 m vorsieht, und § 11 Abs. 2 SBV, welcher bis zu einem Abstand von 5 m vom Ufer eine naturnahe Gestaltung und Nutzung fordert, in Einklang. Dass die Lektüre von § 11 Abs. 2 SBV ohne Beizug des Gestaltungsplans einen anderen Schluss nahelegt, ist nicht entscheidend. Die beiden Planungsinstrumente gehören zusammen und können nicht isoliert betrachtet werden (vgl. § 45 Abs. 1 des Planungs- und Baugesetzes des Kantons Solothurn vom 3. Dezember 1978 [BGS 711.1]).
Die Rüge der willkürlichen Auslegung des Teilzonen- und Gestaltungsplans Fegetzhof mit Sonderbauvorschriften erweist sich damit als unbegründet. Daraus folgt, dass das Verwaltungsgericht das Willkürverbot auch nicht verletzt hat, wenn es bei der Auslegung von <ref-law>/SO auf die im Gestaltungsplan eingezeichnete Baulinie abstellte. Auch diesbezüglich ist die Rüge der Beschwerdeführer unbegründet.
4.4 Insoweit als die Beschwerdeführer eine Verletzung des Grundsatzes von Treu und Glauben geltend machen, ist auf die Beschwerde mangels hinreichender Substanziierung nicht einzutreten (<ref-law>). Der in <ref-law> verankerte Grundsatz verleiht in der Form des sogenannten Vertrauensschutzes den Rechtsunterworfenen einen Anspruch auf Schutz ihres berechtigten Vertrauens in das bestimmte Erwartungen begründende Verhalten der Behörden (<ref-ruling> E. 8.1 S. 60 mit Hinweisen). Eine konkrete behördliche Zusicherung wird jedoch von den Beschwerdeführern nicht dargetan.
5. 5.1 Die Beschwerdeführer rügen eine willkürliche Anwendung von <ref-law>/SO und § 43 Abs. 1 des Gesetzes des Kantons Solothurn vom 27. September 1959 über die Rechte am Wasser (Wasserrechtsgesetz; BGS 712.11). Nach diesen Bestimmungen dürfen Hecken und andere Lebensräume von bedrohten Tier- und Pflanzenarten sowie Ufergehölz weder entfernt noch vermindert werden.
5.2 Im angefochtenen Entscheid wird dazu ausgeführt, dass 2001 im Kanton Solothurn ein Heckenfeststellungsverfahren durchgeführt worden sei. Im Erschliessungsplan seien innerhalb des Gestaltungsplanperimeters weder eine Hecke noch Ufergehölz eingezeichnet, obwohl solches zu dessen Inhalt gehören würde. Grund dafür sei, dass es im Bereich des Rinnsals im Norden des Gestaltungsplanperimeters tatsächlich weder eine Hecke noch Ufergehölz gebe. Insbesondere im Bereich des Retentionsbeckens gebe es vorwiegend junge Pflanzen. Deren Wurzelwerk bilde ausserdem keine Einheit mit dem Rinnsal, sodass ohnehin nicht von Ufergehölz gesprochen werden könne.
5.3 Die Beschwerdeführer bezeichnen die Feststellung, die Pflanzen im Bereich des Retentionsbeckens seien vorwiegend jung, als falsch. Sie verweisen auf zwei Fotos im Bericht zur Abklärung der Hochwassersicherheit für die Überbauung Fegetzhof von BSB + Partner vom 26. Oktober 2005 in der Version "Rev. 1" vom 28. März 2006. Diese Version befindet sich indessen nicht in den Verfahrensakten, sondern wurde von den Beschwerdeführern erstmals im bundesgerichtlichen Verfahren eingereicht (<ref-law>). Das Verwaltungsgericht stützte sich auf die ursprüngliche Version "Rev. 0", worin die beiden Fotos noch nicht enthalten waren. Eine offensichtlich unrichtige oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhende Feststellung des Sachverhalts machen sie diesbezüglich - abgesehen von Behauptung, die Pflanzen im Bereich des Retentionsbeckens seien entgegen den Erwägungen der Vorinstanz nicht vorwiegend jung - nicht geltend (Art. 97 Abs. 1, Art. 105 Abs. 1 und 2 BGG). Zudem ist aufgrund der beiden Fotos nicht klar, inwiefern die abgebildeten Pflanzen vom Bauprojekt tangiert werden (<ref-law>).
Schliesslich weisen die Beschwerdeführer darauf hin, dass die Bäume den Fledermäusen, welche im Dach ihres Hauses wohnten, den nötigen Lebensraum böten. Die Feststellung des Sachverhalts im angefochtenen Entscheid, wo sich für diese Behauptung keine Anhaltspunkte finden, rügen sie indessen nicht. Auch legen sie nicht dar, weshalb erst der Entscheid der Vorinstanz zu dem Vorbringen Anlass gegeben haben sollte (<ref-law>; <ref-ruling> E. 2.2.1 S. 226 mit Hinweis). Unter diesen Umständen ist auf die Rüge der Beschwerdeführer nicht einzutreten.
6. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Diesem Ausgang des Verfahrens entsprechend sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>). Die nicht anwaltlich vertretenen Beschwerdegegner haben keinen Anspruch auf eine Parteientschädigung (Art. 68 Abs. 1 und 2 BGG; <ref-ruling> E. 4 S. 446 mit Hinweis).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien, der Baukommission der Stadt Solothurn, dem Bau- und Justizdepartement und dem Verwaltungsgericht des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 14. Januar 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold