Sachverhalt:
A. Die Baukommission der Stadt Solothurn bewilligte der Swisscom Mobile AG (heute: Swisscom [Schweiz] AG) am 11. Juli 2006 eine Mobilfunk-Antennenanlage für die Frequenzbereiche GSM900 und GSM1800 sowie UMTS an der Allmendstrasse 2a in Solothurn (Parzelle Nr. 5038). Dagegen erhoben A._ und weitere Personen Beschwerde beim Bau- und Justizdepartement des Kantons Solothurn. Während des Beschwerdeverfahrens ersetzte die Bauherrin das bestehende durch ein aktualisiertes, vom 22. Oktober 2007 datierendes Standortdatenblatt. Mit Verfügung vom 23. Mai 2008 wies das Bau- und Justizdepartement die Beschwerde im Wesentlichen ab, soweit es auf sie eintrat. Gegen diesen Entscheid erhoben A._ und weitere Personen Beschwerde an das Verwaltungsgericht des Kantons Solothurn. Beantragt wurde neben der Verweigerung der Baubewilligung unter anderem, es seien die Rechte von 46 Mitunterzeichnenden der Beschwerde an das Bau- und Justizdepartement wieder vollumfänglich herzustellen. Das Verwaltungsgericht trat mit Urteil vom 10. Dezember 2008 auf die Beschwerde von drei Beschwerdeführern nicht ein, jene der übrigen wies es ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 2. Februar 2009 stellt A._ im Namen von "Bewohnern der Gemeinde Solothurn" folgende Rechtsbegehren:
"1. - Die Rechte von 46 Unterzeichnenden unserer Beschwerde Nr. 3 vom 24. Juli 2006 an das Bau- und Justizdepartement sind vollumfänglich wieder herzustellen,
- bzw. die Rechte von 3 Unterzeichnenden unserer Beschwerde Nr. 2 vom 10. Juni 2008 an das Verwaltungsgericht Solothurn sind vollumfänglich wieder herzustellen.
2. Die Verfahrenskosten vor Verwaltungsgericht Solothurn sind neu zu verteilen.
3. Die Beschwerdeführer beantragen eine Parteientschädigung von Fr. 1'200.-- für das Verfahren am Verwaltungsgericht Solothurn.
4. Die Beschwerdeführer beantragen eine Kostenbeteiligung des Verwaltungsgerichts Solothurn für das Verfahren am Bundesgericht.
5. Die Beschwerdeführer beantragen eine weitere Parteientschädigung von Fr. 1'200.-- für das Verfahren am Bundesgericht.
6. Die Baubewilligung und die Betriebsbewilligung für die Mobilfunkantenne für GSM und UMTS mit Basisstation sind aufzuheben.
7. Das Baugesuch Nr. 55/2004 an die Stadt Solothurn ist abzuweisen. Es soll keine Baubewilligung erteilt werden.
8. Eventuell ist das Geschäft an die Vorinstanz zur Begründung, zur Überarbeitung oder zum Neuentscheid zurückzuweisen.
9. Relevante, sachliche Einwände des Beschwerdeführers sind in genügender Tiefe zu beurteilen. Eine allfällige Ablehnung der Einwände ist dichter zu begründen.
10. Es ist das rechtliche Gehör zu gewähren. Die vorgelegten Beweismittel sind entgegenzunehmen, materiell zu behandeln, ihre Auswirkungen auf die bisherige Rechtsprechung zu prüfen und die Sachlage ev. neu zu beurteilen. Eine allfällige Ablehnung der Beweise ist zu begründen.
Es ist feszustellen,
11. dass Gemeinde und Kanton die Kontrollen von Mobilfunkanlagen nicht gewährleisten und dadurch die Einhaltung des Anlagegrenzwerts nicht gewährleisten.
12. dass die Grenzwerte der NISV den Vorsorgeauftrag der Bundesverfassung und des Umweltschutzgesetzes verletzen."
Das Verwaltungsgericht, das Bau- und Justizdepartement, die Baukommission sowie die Swisscom (Schweiz) AG beantragen in ihrer jeweiligen Vernehmlassung, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Die F._ AG verzichtet auf eine Stellungnahme. Das Bundesamt für Umwelt (BAFU) kommt in seiner Vernehmlassung zum Schluss, dass im angefochtenen Entscheid das Umweltrecht des Bundes richtig angewendet worden sei.

Erwägungen:
1. 1.1 Beim angefochtenen Urteil handelt es sich um einen kantonal letztinstanzlichen Entscheid über eine Mobilfunkanlage, welcher der Beschwerde in öffentlich-rechtlichen Angelegenheiten unterliegt (Art. 82 ff. BGG). Die Beschwerdeführer wohnen innerhalb des praxisgemäss berechneten Einspracheradius. Sie werden vom umstrittenen Bauvorhaben besonders berührt und haben ein schutzwürdiges Interesse an der Aufhebung oder Änderung des Urteils des Verwaltungsgerichts (Art. 89 Abs. 1 lit. b und c BGG; <ref-ruling> E. 2 S. 169 ff. mit Hinweisen). Auf die Beschwerde ist unter Vorbehalt der nachfolgenden Erwägungen einzutreten.
1.2 Nach Art. 42 Abs. 2 BGG ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt. Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (Art. 106 Abs. 1 BGG). Das setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die Begründungsanforderungen von Art. 42 Abs. 2 BGG erfüllt.
Strengere Anforderungen gelten, wenn die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung) geltend gemacht wird. Dies prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG). Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Erlass oder Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen. 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. 1.6 S. 130; <ref-ruling> E. 2.1 und 2.2 S. 245 f.; je mit Hinweisen).
1.3 Die Beschwerde wird laut Beschwerdeschrift von "Bewohnern der Gemeinde Solothurn" geführt. Dem Bundesgericht wurden Vollmachten von fünf Personen eingereicht (vgl. Art. 40 Abs. 2 BGG). Zur Beschwerde in öffentlich-rechtlichen Angelegenheiten ist nach Art. 89 Abs. 1 lit. a BGG nur berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat. Alle fünf Beschwerdeführer haben am Verfahren vor Verwaltungsgericht teilgenommen.
Die Beschwerde der Beschwerdeführerin 5 behandelte das Verwaltungsgericht indessen nur insofern, als diese rügte, zu Unrecht vom Verfahren vor dem Bau- und Justizdepartement ausgeschlossen worden zu sein. Im Ergebnis wies das Verwaltungsgericht ihre Beschwerde ab. Es führte aus, aufgrund der verschiedenen Beschwerdeschriften und in Etappen eingereichten Vollmachten, dem Umstand, dass die Beschwerdeführer zum Teil mehrere Vollmachten unterschrieben und diese zum Teil wieder zurückzogen hätten, sei eine Klärung der Frage, wer vor dem Bau- und Justizdepartement tatsächlich Beschwerde führte, dringend angezeigt gewesen. Das Bau- und Justizdepartement habe den Vertreter deshalb zu Recht aufgefordert, eine allfällige Korrektur der Tabelle mit den Beschwerdeführern bekannt zu geben. Eine Reaktion auf diese Verfügung sei ausgeblieben. Damit hätten die betroffenen Beschwerdeführer, darunter die Beschwerdeführerin 5, ihre Mitwirkungspflicht verletzt.
Auf diese Begründung des vorinstanzlichen Entscheids wird in der Beschwerde an das Bundesgericht nicht in rechtsgenüglicher Weise eingegangen. Auf die Rüge, der Ausschluss vom Verfahren sei willkürlich und stelle eine Rechtsverweigerung dar, ist deshalb nicht einzutreten. Damit entfällt für die Beschwerdeführerin 5 die formelle Beschwer insgesamt, also auch im Hinblick auf die weiteren in der Beschwerdeschrift vorgetragenen Rügen (Art. 89 Abs. 1 lit. a BGG). Auf ihre Beschwerde ist nicht einzutreten.
1.4 Die Beschwerdeführer rügen, im vorinstanzlichen Verfahren sei eine Anzahl weiterer Personen zu Unrecht vom Verfahren ausgeschlossen worden. Da es sich bei diesen ausschliesslich um Dritte handelt, fehlt den Beschwerdeführern die erforderliche Beschwer (Art. 89 Abs. 1 lit. b und c BGG). Auf die Rüge ist nicht einzutreten.
Soweit die Beschwerdeführer in diesem Zusammenhang auch den Entscheid des Bau- und Justizdepartements rügen, ist darauf im Übrigen auch deshalb nicht einzutreten, weil im Verfahren vor Bundesgericht ausschliesslich der Entscheid des Verwaltungsgerichts Anfechtungsgegenstand bildet (Art. 86 Abs. 1 lit. d BGG; <ref-ruling> E. 1.4 S. 144 mit Hinweis).
1.5 Die Beschwerdeführer beantragen, es sei festzustellen, "dass Gemeinde und Kanton die Kontrollen von Mobilfunkanlagen nicht gewährleisten und dadurch die Einhaltung des Anlagegrenzwertes nicht gewährleisten" sowie "dass die Grenzwerte der NISV den Vorsorgeauftrag der Bundesverfassung und des Umweltschutzgesetzes verletzen". Ein Interesse an einer derartigen Feststellung, welches über das Interesse an der Gutheissung der übrigen Rechtsbegehren hinausgeht, wird nicht dargetan und ist auch nicht erkennbar. Auf das Feststellungsbegehren ist nicht einzutreten (<ref-ruling> E. 1c S. 491 mit Hinweis; Urteil 1C_62/2009 vom 25. Mai 2009 E. 1.1).
1.6 Die Beschwerdeführer rügten im Verfahren vor Verwaltungsgericht eine Verletzung ihres Anspruchs auf rechtliches Gehör durch das Bau- und Justizdepartement (Art. 29 Abs. 2 BV). Die entscheidende Verwaltungsbehörde habe zu begründen, warum sie den in den vorgelegten Beweisdokumenten dargelegten Ansichten nicht folge. Zudem sei der in Frage stehende Einwand, dass der wissenschaftliche Beweis einer Gesundheitsschädigung nicht erforderlich sei, zentral. Die Rüge wird im bundesgerichtlichen Verfahren wiederholt.
Das Verwaltungsgericht bemerkte zu den von den Beschwerdeführern eingereichten Studien, dass medizinisch (noch) nicht hinreichend geklärt sei, wie sich nichtionisierende Strahlung von Mobilfunkanlagen auf die Gesundheit auswirke. Es wies unter anderem auf einen neueren Entscheid des Bundesgerichts hin, wonach auch neuere Forschungen keine Evidenz für gesundheitliche Wirkungen von Hochfrequenzstrahlung im Niedrigdosisbereich durch Mobilfunkbasisstationen ergeben habe.
Es gehört zu den Obliegenheiten der Prozessparteien, im Einzelnen aufzuzeigen, was sie mit welchen Beweismitteln nachweisen wollen bzw. wollten. Die Beschwerdeführer beschränken sich auf den Hinweis, es sei ein zentraler Einwand, dass der wissenschaftliche Beweis einer Gesundheitsschädigung nicht erforderlich sei. Zudem führen sie eine Liste von Dokumenten an, mit denen sich die Vorinstanzen ihrer Ansicht nach hätten auseinandersetzen sollen. Diese pauschale Kritik am angefochtenen Entscheid genügt den Begründungsanforderungen von Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG nicht. Auf die Rüge der Verletzung des rechtlichen Gehörs ist nicht einzutreten.
Soweit die Beschwerdeführer in diesem Zusammenhang auch eine Verletzung der Untersuchungspflicht nach kantonalem Verfahrensrecht geltend machen, tragen sie keinen nach Art. 95 ff. BGG zulässigen Beschwerdegrund vor. Darauf ist ebenfalls nicht einzutreten.
1.7 Die Beschwerdeführer betrachten alle vom Bund verfassten Schriften und von ihm in Auftrag gegebenen Studien als unzulässig. Die Studie des vormaligen Bundesamts für Umwelt, Wald und Landschaft (BUWAL [Hrsg.], Hochfrequente Strahlung und Gesundheit; Bewertung von wissenschaftlichen Studien an Menschen im Niedrigdosisbereich, 2003, «http://www.bafu.admin.ch/publikationen» [besucht am 24. Juni 2009]) sei "aus dem Protokoll zu streichen". Der Bund sei Hauptaktionär der Swisscom und deshalb befangen.
Die Beschwerdeführer zeigen nicht auf, inwiefern der angefochtene Entscheid in diesem Punkt Rechtsnormen verletzt (Art. 95 ff. BGG). Die Beweiswürdigung ist Teil der Feststellung des Sachverhalts, welche nur unter den Voraussetzungen von Art. 97 Abs. 1 BGG gerügt werden kann. Auf das nicht hinreichend substanziierte Vorbringen ist nicht einzutreten (Art. 42 Abs. 2 BGG).
1.8 Vor Verwaltungsgericht hatten die Beschwerdeführer beantragt, die Betreiberin der Anlage sei zu verpflichten, bei Beginn einer Überbauung der benachbarten Parzelle Nr. 1189 die Sendeleistung soweit zu reduzieren, dass die Grenzwerte der Verordnung vom 23. Dezember 1999 über den Schutz vor nichtionisierender Strahlung (NISV; SR 814.710) eingehalten würden. Die Aufzählung der Orte mit empfindlicher Nutzung (OMEN, vgl. Art. 3 Abs. 3 NISV) in Ziff. 5 Satz 2 des Entscheids der Baukommission vom 11. Juli 2006 sei entsprechend um einen weiteren OMEN zu ergänzen. Die Parzelle Nr. 1189 könne überbaut werden und die für diesen Ort errechnete Feldstärke liege nahe am Anlagegrenzwert.
Das Verwaltungsgericht legte dar, dass unüberbaute, eingezonte Grundstücke, auf denen empfindliche Nutzungen zulässig seien, so behandelt würden, als wären die Gebäude bereits errichtet. Bestehe noch keine Planung, so gelte das gesamte baurechtlich zulässige Volumen als OMEN. Die im Standortdatenblatt notwendigerweise enthaltenen Angaben umfassten die von der Anlage erzeugte Strahlung an den drei Orten mit empfindlicher Nutzung, an denen diese Strahlung am stärksten sei, und an allen Orten mit empfindlicher Nutzung, an denen der Anlagegrenzwert überschritten werde (Art. 11 Abs. 2 lit. c Ziff. 2 und 3 NISV). Beides treffe für die Parzelle Nr. 1189 nicht zu. Im Standortdatenblatt sei deshalb zu Recht kein weiterer OMEN aufgeführt.
Abgesehen vom Vorwurf, dass die Argumentation des Verwaltungsgerichts an ihrem Einwand völlig vorbeigehe, setzen sich die Beschwerdeführer in keiner Weise mit eben dieser Argumentation auseinander. Auf die Rüge ist nicht einzutreten (Art. 42 Abs. 2 BGG).
1.9 Wie bereits vor Verwaltungsgericht verlangen die Beschwerdeführer auch im bundesgerichtlichen Verfahren, es sei nach Inbetriebnahme der Mobilfunkanlage für alle OMEN eine Abnahmemessung durchzuführen. Das Verwaltungsgericht legte im angefochtenen Entscheid dar, an welchen OMEN und weshalb eine Abnahmemessung erforderlich sei. Einer Abnahmemessung bedürfe es in der Regel dann, wenn gemäss der rechnerischen Prognose die Strahlenbelastung 80 % des Anlagegrenzwerts erreiche. Darauf gehen die Beschwerdeführer nicht ein. Sie behaupten, die maximale Leistung könne nicht auf 20 % genau berechnet werden. Weder begründen sie diese Behauptung (Art. 42 Abs. 2 BGG) noch führen sie einen nach Art. 95 ff. BGG zulässigen Beschwerdegrund an. Ihre Ausführungen zur Ungenauigkeit der Messung sind in diesem Zusammenhang nicht von Bedeutung, denn die Berechnung der Strahlung ist von deren Messung zu unterscheiden (vgl. Urteil 1C_132/2007 vom 30. Januar 2008 E. 4.5). Auf die Rüge ist nicht einzutreten.
1.10 Die Beschwerdeführer machten vor Verwaltungsgericht geltend, UMTS-Strahlung könne nicht genügend exakt gemessen werden. Die Baubewilligung sei deshalb zu verweigern. Das Verwaltungsgericht wies diesbezüglich auf die bundesgerichtliche Rechtsprechung hin, wonach heute Messsysteme existieren, die UMTS-Strahlung zuverlässig messen können. Darauf gehen die Beschwerdeführer lediglich insofern ein, als sie diese Rechtsprechung in pauschaler Weise ablehnen. Auf das Vorbringen ist nicht einzutreten (Art. 42 Abs. 2 BGG).
1.11 Die Beschwerdeführer bringen vor, eventuell könne das Messsystem unter der Auflage eines Sicherheitsfaktors von 1.82 bewilligt werden. Dieses Begehren ist neu und deshalb unzulässig (Art. 99 Abs. 2 BGG). Im Übrigen ist auf die einlässliche Auseinandersetzung mit der Berücksichtigung von Messunsicherheiten im Urteil des Bundesgerichts 1C_132/2007 vom 30. Januar 2008 hinzuweisen (a.a.O., E. 4.4-4.6 mit Hinweisen).
2. 2.1 Die Beschwerdeführer rügen, das Qualitätssicherungssystem der Mobilfunknetzbetreiberin sei ungenügend. Wie schon vor dem Verwaltungsgericht bringen sie vor, für die Durchführung der Abnahme- und Kontrollmessungen müsse die Anlage durch das Messpersonal selbst gesteuert werden können. Die für die Messungen notwendigen Informationen müssten vollautomatisch übermittelt werden können. Manipulationen durch Mitarbeiter der Mobilfunknetzbetreiberin müssten ausgeschlossen werden. Die Beschwerdeführer beantragten in diesem Zusammenhang im vorinstanzlichen Verfahren zwei Augenscheine. Beim ersten hätte der Kanton Solothurn beweisen sollen, dass er über die für die Kontrolle notwendige Hard- und Software sowie das Personal verfüge. Beim zweiten hätte er aufzeigen müssen, dass bei der Mobilfunknetzbetreiberin eine ordentlich geführte Datenbank und das erforderliche Personal vorhanden seien.
2.2 In Antwort auf diese Vorbringen legte die Vorinstanz die bundesgerichtliche Rechtsprechung zu den bestehenden Qualitätssicherungssystemen dar. Sie kam zum Schluss, eine geeignete Kontrolle sei gewährleistet und lehnte den Antrag auf Durchführung der zwei Augenscheine ab.
2.3 Die Qualitätssicherungssysteme dienen der Kontrolle, dass die bewilligten Parameter (äquivalente Strahlungsleistung ERP, Senderichtung) der Mobilfunkantennen im Betrieb eingehalten und die Grenzwerte der NISV nicht überschritten werden. Diese Kontrolle ist in Art. 12 NISV vorgesehen. Die Verordnung schreibt jedoch nicht vor, auf welche Weise sie zu erfolgen hat. Das Bundesgericht hatte letztmals in seinem Urteil 1C_282/2008 vom 7. April 2009 Gelegenheit, zu den bestehenden Qualitätssicherungssystemen Stellung zu nehmen. Es wies auf die 2007 durchgeführte Überprüfung der Qualitätssicherungssysteme der Mobilfunknetzbetreiber Orange, Sunrise, Swisscom und Tele2 hin. Es räumte ein, die Systeme wiesen noch Mängel auf. Insgesamt kam es jedoch zum Schluss, dass diese aus umweltschutzrechtlicher Sicht nicht zu beanstanden seien (a.a.O., E. 3). Die Kritik der Beschwerdeführer gibt keinen Anlass, auf diese Rechtsprechung zurückzukommen. Die Rüge, das zur Anwendung kommende Qualitätssicherungssystem sei ungenügend, ist demnach abzuweisen.
Auf den auch im bundesgerichtlichen Verfahren aufrechterhaltenen Antrag der Beschwerdeführer, es seien zwei Augenscheine anzuordnen, ist nicht einzutreten. Die Beschwerdeführer legen nicht dar, inwiefern der angefochtene Entscheid in diesem Punkt Recht verletzt (Art. 42 Abs. 2 BGG).
3. 3.1 Nach Ansicht der Beschwerdeführer liegen genügend epidemiologische Studien vor, die nachweisen, dass die Grenzwerte der NISV zu hoch angesetzt sind. Bis zum Erlass tieferer Anlagegrenzwerte durch den Bundesrat sei die Baubewilligung zu sistieren. Die Beschwerdeführer berufen sich auf das Vorsorgeprinzip (Art. 74 Abs. 2 Satz 1 BV; Art. 1 Abs. 2 USG) und das Recht auf körperliche und geistige Unversehrtheit nach Art. 10 Abs. 2 BV.
3.2 Die Anlage- und Immissionsgrenzwerte der NISV hat das Bundesgericht bisher stets als gesetzes- und verfassungskonform beurteilt (Urteile 1C_282/2008 vom 7. April 2009 E. 4; 1C_92/2008 vom 16. Dezember 2008 E. 3.3-3.6; 1C_316/2007 vom 30. April 2008 E. 5.1; 1C_170/2007 vom 20. Februar 2008 E. 2; je mit Hinweisen). Auch neuere Forschungen haben keine wissenschaftlich genügenden Studien hervorgebracht, welche einen hinreichenden Zusammenhang zwischen der Exposition durch Mobilfunkbasisstationen und schädlichen oder lästigen Einwirkungen herstellen (vgl. BAFU [Hrsg.], Hochfrequente Strahlung und Gesundheit; Bewertung von wissenschaftlichen Studien im Niedrigdosisbereich; 2. Aufl. 2007, S. 10 ff., 72 f., 98 ff., 105 f. und 131; «http://www.bafu.admin.ch/publikationen» [besucht am 24. Juni 2009]) Die wissenschaftliche Datenlage für die Beurteilung der Gesundheitsgefährdung der Bevölkerung durch hochfrequente Strahlung im Niedrigdosisbereich, namentlich durch Mobilfunkbasisstationen, ist noch immer sehr lückenhaft. Forschung auf diesem Gebiet ist deshalb besonders wichtig. Die bestehenden Wissenslücken rechtfertigen es jedoch nicht, die Grenzwerte der NISV als rechtswidrig zu beurteilen und den weiteren Bau von Mobilfunkantennen zu verbieten (Urteil 1C_170/2007 vom 20. Februar 2008 E. 2).
Es ist in erster Linie Sache der zuständigen Fachbehörden (und nicht des Bundesgerichts), die internationale Forschung sowie die technische Entwicklung zu verfolgen und gegebenenfalls eine Anpassung der Grenzwerte der NISV zu beantragen (Urteil 1C_316/2007 vom 30. April 2008 E. 5.1 mit Hinweis). Die Beschwerdeführer zitieren einige Studien und führen gesundheitliche Beschwerden auf, welche bereits mehrfach nachgewiesen sein sollen. Sie vermögen damit nicht aufzuzeigen, dass die zuständigen Fachbehörden oder der Bundesrat als Verordnungsgeber untätig geblieben sind und es unterlassen haben, eine gebotene Anpassung der Grenzwerte zu beantragen bzw. vorzunehmen.
Die kantonalen Behörden haben damit zu Recht die geltenden Immissions- und Anlagegrenzwerte der NISV angewandt. Die Rüge der Beschwerdeführer erweist sich als unbegründet.
4. Zusammenfassend ergibt sich, dass auf die Beschwerde der Beschwerdeführerin 5 nicht einzutreten ist und dass die Beschwerde der Beschwerdeführer 1 bis 4 abzuweisen ist, soweit darauf eingetreten werden kann. Dem Ausgang des bundesgerichtlichen Verfahrens entsprechend sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (Art. 66 Abs. 1 BGG). Da die obsiegende, anwaltlich vertretene Beschwerdegegnerin auf eine Vernehmlassung verzichtet hat, hat sie keinen Anspruch auf eine Parteientschädigung.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 4'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 sowie dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 6. Juli 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold