Sachverhalt:
A. Mit Verfügungen des damaligen kantonalen Baudepartements (heute: Bau- und Justizdepartement) vom 4. März 1987 und der Baukommission Matzendorf vom 23. März 1987 wurde der Umbau des Schützenhauses Matzendorf bewilligt (Anbau und Sanierung sowie Schaffung von Parkplätzen). Das Baudepartement ordnete - als Auflage zur Ausnahmebewilligung nach Art. 24 RPG (SR 700) - explizit die Erstellung einer in den Bauplänen vorgesehenen Lärmschutzwand an. Diese ist bis heute nicht errichtet worden.
B. Am 22. Februar 2007 publizierte die Baukommission der Gemeinde Matzendorf ein Baugesuch für die Erneuerung der Nummerierung ihres zum Schiessstand gehörenden Scheibenstands. Die Eheleute X._ erhoben als von einer Überschreitung des Immissionsgrenzwerts betroffene Anwohner während der Auflagefrist Einsprache gegen das Bauvorhaben. Sie beantragten die Rückweisung des Baugesuchs an die Gemeinde zur Vervollständigung und Verbesserung sowie eventualiter die Abweisung des Baugesuchs. Zudem verlangten sie in einer ergänzenden Eingabe vom 29. März 2007 den teilweisen Widerruf früherer Bewilligungen der kantonalen und kommunalen Behörden, wie sie der heutigen Schiessanlage und deren Betrieb zugrunde liegen. Insbesondere beantragten sie:
"2.1 Die Verfügungen des Bau- und Justizdepartementes vom 4. März 1987 so- wie diejenige der Baukommission Matzendorf vom 23. März 1987 seien in- soweit teilweise zu widerrufen, als mit ihnen ein Schiessbetrieb mit einem maximalen Äquivalent von jährlich 15'000 Schüssen und 25 gewichteten Schiesshalbtagen bewilligt bzw. Sanierungserleichterungen gewährt wurden, und es sei der Betrieb der Schiessanlage auf das lärmschutzrechtlich zuläs- sige Mass zu reduzieren bzw. innert angemessener Frist einzustellen.
2.2 Eventualiter sei der Schiessbetrieb auf die vom Bund unterstützten Schiess- anlässe zu reduzieren, und es sei die Gesuchstellerin zu verpflichten, die gemäss Verfügung vom 4. März 1987 auferlegte Lärmschutzwand umgehend zu erstellen, verbunden mit der Androhung, dass im UnterlassungsfaIl ein Vollstreckungsverfahren beim zuständigen Oberamtmann eingeleitet werde.
2.3 Subeventualiter sei der Schiessbetrieb auf das mit Verfügung des Bau- und Justizdepartements vom 4. März 1987 bzw. 10. Mai 2004 definierte Mass zu reduzieren und die Gesuchstellerin zu verpflichten, die gemäss Verfü- gung vom 4. März 1987 auferlegte Lärmschutzwand umgehend zu erstel- len, verbunden mit der Androhung, dass im Unterlassungsfall ein Vollstre- ckungsverfahren beim zuständigen Oberamtmann eingeleitet werde."
Mit Verfügungen vom 25. September 2008 schrieb das Bau- und Justizdepartement die Einsprache gegen die Erneuerung der Nummerierung als gegenstandslos geworden ab und trat auf die Begehren 2.1 bis 2.3 zur Behebung des rechtswidrigen Zustands nicht ein. Den Entscheid, auf die Begehren 2.1 bis 2.3 nicht einzutreten, begründete das Bau- und Justizdepartement mit der fehlenden Parteistellung der Eheleute X._, weil ihnen lediglich die Rechtsstellung von Anzeigern zukomme. Gleichzeitig widerrief das Departement die Ausnahmebewilligung vom 4. März 1987 insofern teilweise, als die einzuhaltende Pegelkorrektur verschärft wurde. Ausserdem stellte es ein Vollstreckungsgesuch wegen der nicht erstellten, aber bereits 1987 verlangten Lärmschutzwand in Aussicht.
Gegen die Verfügungen des Departements vom 25. September 2008 gelangten die Eheleute X._ an das Verwaltungsgericht des Kantons Solothurn, welches die Beschwerde mit Urteil vom 2. März 2009 abwies, soweit es darauf eintreten konnte.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 22. April 2009 beantragen die Eheleute X._ im Wesentlichen die Aufhebung des Urteils des Verwaltungsgerichts vom 2. März 2009 und der zugrunde liegenden kantonalen und kommunalen Entscheide sowie die Rückweisung der Sache an das Bau- und Justizdepartement zur materiellen Beurteilung ihrer Begehren. Eventualiter sei die Sache an das Verwaltungsgericht zurückzuweisen und subeventualiter solle das Bundesgericht den Betrieb der Schiessanlage auf das lärmschutzrechtlich zulässige Mass reduzieren.
D. Das kantonale Bau- und Justizdepartement beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde. Die Gemeinde Matzendorf und die örtliche Schiessplatzkommission liessen sich nicht vernehmen.
Das Bundesamt für Umwelt (BAFU) kommt zum Schluss, dass die Anzahl der bewilligten Schiesshalbtage erheblich von den Richtwerten der eidgenössischen Schiessverordnung vom 5. Dezember 2003 (SR 512.31) abweiche. Es hält eine Begrenzung auf die in der Schiessverordnung erwähnten maximal sieben Schiesshalbtage für die Vereinstrainings und die Schiesswettkämpfe als angemessen.
Das Verwaltungsgericht verzichtet auf eine Stellungnahme zu den Ausführungen des BAFU. Das Bau- und Justizdepartement und die Beschwerdeführer halten an ihren Standpunkten fest.

Erwägungen:
1. 1.1 Dem angefochtenen Entscheid liegt ein bau- und umweltrechtliches Verfahren betreffend die Sanierung der Schiessanlage in Matzendorf zugrunde. Umstritten ist im Wesentlichen die Parteistellung der Beschwerdeführer. Damit liegt eine Streitigkeit vor, welche im Rahmen der Beschwerde in öffentlich-rechtlichen Angelegenheiten zu beurteilen ist (<ref-law>). Das Verwaltungsgericht hat als letzte kantonale Instanz entschieden (<ref-law>). Die Rüge, das Verwaltungsgericht habe zu Unrecht die Parteistellung der Beschwerdeführer verneint und damit <ref-law> verletzt, ist zulässig (<ref-law>). Zur Rüge der formellen Rechtsverweigerung sind die Beschwerdeführer im bundesgerichtlichen Verfahren ungeachtet ihrer Legitimation in der Sache berechtigt (<ref-law>, vgl. <ref-ruling> E. 2.3 S. 301; <ref-ruling> E. 3b S. 167).
1.2 Unzulässig ist der Antrag der Beschwerdeführer, auch die unterinstanzlichen Entscheide des Bau- und Justizdepartements sowie der Baukommission Matzendorf 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.3 Die übrigen Sachurteilsvoraussetzungen sind erfüllt, weshalb auf die Beschwerde unter Vorbehalt der Ausführungen in E. 1.2 hiervor einzutreten ist.
2. Aus den Verfahrensakten ergibt sich, dass der Schiessbetrieb zu einer Überschreitung der massgebenden Immissionsgrenzwerte bei der Liegenschaft der Beschwerdeführer führt und dass die in den Verfügungen des damaligen kantonalen Baudepartements vom 4. März 1987 und der Baukommission Matzendorf vom 23. März 1987 angeordnete Lärmschutzwand nicht errichtet wurde. Die Beschwerdeführer verlangten im kantonalen Verfahren in Ziff. 2.1 bis 2.3 ihrer Anträge Betriebsbeschränkungen unter teilweisem "Widerruf" der Bewilligungen von 1987. Das Verwaltungsgericht kam zum Schluss, die rechtskräftigen Verfügungen könnten nicht auf Gesuch der heutigen Beschwerdeführer hin in Wiedererwägung gezogen werden, da diese im Bewilligungsverfahren nicht Partei gewesen seien. Zudem habe das Bau- und Justizdepartement bereits am 10. Mai 2004 entschieden, dass die Schiessanlage im Umfang der bewilligten Nutzung in lärmschutzrechtlicher Hinsicht nicht als sanierungsbedürftig zu gelten habe.
2.1 Ausgangspunkt für die Beurteilung der vorliegenden Angelegenheit ist der Grundsatz der Einheit des Verfahrens. Nach <ref-law> muss sich am Verfahren vor allen kantonalen Vorinstanzen als Partei beteiligen können, wer zur Beschwerde an das Bundesgericht berechtigt ist. Die kantonalen Behörden dürfen die Rechtsmittelbefugnis nicht enger fassen, als dies für die Beschwerde an das Bundesgericht vorgesehen ist (vgl. Urteil des Bundesgerichts 1C_379/2008 vom 12. Januar 2009 E. 3.2 mit Hinweisen). Zur Beurteilung, ob die Vorinstanz die Beschwerdeführer vom Rechtsmittel ausschliessen durfte, ist im vorliegenden Fall die Beschwerdeberechtigung nach den Grundsätzen von <ref-law> zu prüfen (Urteil des Bundesgerichts 1C_26/2009 vom 27. Februar 2009 E. 2.1 mit Hinweisen).
Zur Beschwerde in öffentlich-rechtlichen Angelegenheiten ist nach <ref-law> berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a); durch den angefochtenen Entscheid oder Erlass besonders berührt ist (lit. b); und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat (lit. c). Die Voraussetzungen von <ref-law> hängen eng zusammen; insgesamt kann insoweit an die Grundsätze angeknüpft werden, die zur Legitimationspraxis bei der Verwaltungsgerichtsbeschwerde nach Art. 103 lit. a OG entwickelt worden sind (vgl. <ref-ruling> E. 2a S. 51 f., 379 E. 4b S. 386 f.). Diese Anforderungen sollen die Popularbeschwerde ausschliessen. Will ein Nachbar eine Baubewilligung anfechten, muss er glaubhaft darlegen, dass er namentlich in räumlicher Hinsicht eine besondere Beziehungsnähe zum Streitgegenstand aufweist und dass seine tatsächliche oder rechtliche Situation durch den Ausgang des Verfahrens beeinflusst werden kann (<ref-ruling> E. 1.3.1 S. 252). Eine besondere Betroffenheit wird vor allem in Fällen bejaht, in welchen von einer Anlage mit Sicherheit oder grosser Wahrscheinlichkeit Immissionen auf das Nachbargrundstück ausgehen (<ref-ruling> E. 2b S. 174; <ref-ruling> E. 4c S. 387). Bei grossflächigen Immissionen kann ein sehr weiter Kreis Betroffener zur Beschwerdeführung legitimiert sein (z.B. Anwohner eines Flughafens: <ref-ruling> E. 3a S. 303 f.; <ref-ruling> E. 3b S. 318; einer Schiessanlage: <ref-ruling> E. 3.2.2 S. 188 mit Hinweisen; eines Fabrikgebäudes für die Verarbeitung gentechnisch veränderter Mikroorganismen: BGE <ref-ruling> E. 4c S. 387 mit weiteren Hinweisen; s. auch <ref-ruling> E. 2b S. 178). In dicht besiedelten Gebieten kann somit grundsätzlich sehr vielen Personen die Beschwerdelegitimation zukommen, ohne dass von einer Popularbeschwerde gesprochen werden müsste (<ref-ruling> E. 2b S. 178; <ref-ruling> E. 4c S. 387; <ref-ruling> E. 1c S. 102; je mit weiteren Hinweisen).
2.2 Die erwähnte bundesgerichtliche Praxis zum Beschwerderecht kann grundsätzlich auch auf Fälle übertragen werden, in welchen betroffene Privatpersonen von der zuständigen Behörde den Erlass einer Verfügung verlangen und - falls die Behörde in einem solchen Fall untätig bleibt - Rechtsverweigerungsbeschwerde erheben, um auf diese Weise den Vollzug des Umweltrechts im Einzelfall zu erzwingen (vgl. Trüeb, Rechtsschutz gegen Luftverunreinigung und Lärm, Zürich 1990, S. 205 ff.; Gächter, Durchsetzung von Sanierungspflichten mittels Rechtsverweigerungsbeschwerde, in: Umweltrecht in der Praxis [URP] 2005 S. 775 ff.). Voraussetzung für eine Rechtsverweigerungsbeschwerde ist, dass die Rechtssuchenden zuvor ein Begehren auf Erlass einer Verfügung bei der zuständigen Behörde gestellt haben und ein Anspruch auf Erlass einer solchen Verfügung besteht (Kölz/Häner, Verwaltungsverfahren und Verwaltungsrechtspflege des Bundes, 2. Aufl. 1998, S. 255; Moser/Uebersax, Prozessieren vor eidgenössischen Rekurskommissionen, 1998, Rz. 5.1 ff.). Ein solcher Anspruch besteht unter anderem dann, wenn die gesuchstellende Person Parteistellung beanspruchen kann (Kölz/Häner, a.a.O., S. 78, S. 255). Fehlt es einer Person, welche ausdrücklich den Erlass einer Verfügung verlangt hat, an der Parteieigenschaft, hat die Behörde eine anfechtbare Nichteintretensverfügung zu erlassen (vgl. zum Ganzen <ref-ruling> E. 2.5 S. 525 f. mit Hinweisen; Urteil des Bundesgerichts 1C_437/2007 vom 3. März 2009 E. 2.3).
2.3 Es ist unbestritten, dass die Beschwerdeführer mehr als jedermann von einer erheblichen Lärmbelastung betroffen sind. Sie können somit Parteistellung im Sinne von <ref-law> sowie das Beschwerderecht gemäss <ref-law> beanspruchen und von der zuständigen Behörde den Erlass einschränkender Anordnungen verlangen. Diese Befugnis ergibt sich unabhängig von der Parteistellung im kantonalen Baubewilligungsverfahren bereits aus dem verfahrensrechtlich geschützten Interesse an der Einhaltung der Rechtsordnung, soweit diese dem Betroffenen einen Schutz vor schädlichen oder lästigen Einwirkungen bietet. Der Betroffene hat insoweit nicht bloss die Stellung eines Anzeigers, sondern besitzt gestützt auf das Umweltschutzrecht des Bundes (insbesondere <ref-law>) einen Anspruch auf Erlass einer Verfügung (<ref-ruling> E. 2c S. 303 mit Hinweisen; vgl. auch <ref-ruling> E. 2.5 S. 525 f.; Urteil des Bundesgerichts 1A.108/2004 vom 17. November 2004 E. 2.3).
2.4 Diesem Anspruch auf eine Verfügung steht nicht entgegen, dass das zuständige Departement die lärmschutzrechtliche Zulässigkeit der Schiessanlage bereits in den Jahren 1987 und 2004 beurteilte. Die Beschwerdeführer haben jedenfalls Anspruch auf die materielle Prüfung ihrer Anträge. Grundsätzlich sind einmal gewährte Sanierungserleichterungen nicht unwiderruflich. Dies hat auch das kantonale Departement erkannt, indem es in seiner Verfügung vom 25. September 2008 unter anderem die Pegelkorrektur verschärfte. Erleichterungen können von Gesetzes wegen auch bei einem Umbau oder einer Erweiterung einer sanierungsbedürftigen Anlage eingeschränkt oder aufgehoben werden (<ref-law>). Nach der bundesgerichtlichen Rechtsprechung können Verfügungen über Dauerrechtsverhältnisse zudem insbesondere wegen unrichtiger Sachverhaltsfeststellung, fehlerhafter Rechtsanwendung oder nachträglicher Änderung der Sach- oder Rechtslage widerrufen werden, sofern wichtige öffentliche Interessen berührt sind. Wo besonders wichtige öffentliche Interessen, wie etwa Polizeigüter, auf dem Spiel stehen, kann sogar eine blosse Praxisänderung Anlass zur Umgestaltung von dauernden Rechtsverhältnissen geben (<ref-ruling> E. 7a S. 313 f. mit Hinweisen).
Das Bundesgericht hat in konstanter Rechtsprechung entschieden, dass mit umweltrechtlichen Immissionsschutzvorschriften gewichtige öffentliche Interessen gewahrt werden (<ref-ruling> E. 5e/aa S. 598; <ref-ruling> E. 4c/cc S. 331; <ref-ruling> E. 3a S. 237; <ref-ruling> E. 1c S. 42; je mit Hinweisen). Fehlen positivrechtliche Bestimmungen über die Möglichkeit der Änderung einer Verfügung, so ist über diese anhand einer Interessenabwägung zu befinden, bei welcher das Interesse an der richtigen Anwendung des objektiven Rechts dem Interesse an der Rechtssicherheit bzw. dem Vertrauensschutz gegenüberzustellen ist (<ref-ruling> E. 7a S. 313 f. mit Hinweisen). Im Rahmen einer solchen Interessenabwägung ist auch das Verhalten des Bewilligungsnehmers zu würdigen, der im vorliegenden Fall ohne erkennbaren Grund während über 20 Jahren auf die Errichtung der in den Bewilligungen von 1987 angeordneten Lärmschutzwand verzichtete. Zudem werden das Ausmass der Lärmbelastung sowie die Ausführungen des BAFU vom 19. August 2009 zu berücksichtigen sein. Darin wird in Bezug auf die beanspruchten Schiesshalbtage auf eine erhebliche Abweichung vom Richtwert der Schiessverordnung hingewiesen.
3. Zusammenfassend ergibt sich, dass das Verwaltungsgericht die Parteistellung der Beschwerdeführer zu Unrecht verneint hat. Die Beschwerde ist somit gutzuheissen und der vorinstanzliche Entscheid aufzuheben. Die Sache ist in Anwendung von <ref-law> zur materiellen Prüfung der Anträge 2.1 bis 2.3 der Beschwerdeführer zur Beseitigung des rechtswidrigen Zustands an das Bau- und Justizdepartement zurückzuweisen.
Im Kostenpunkt ist die Sache zur Neuregelung der Kostenfolgen des kantonalen Verfahrens an das Verwaltungsgericht zurückzuweisen (Art. 67 und 68 Abs. 5 BGG).
Der unterliegenden Gemeinde Matzendorf sind keine Gerichtskosten für das bundesgerichtliche Verfahren aufzuerlegen (<ref-law>). Sie hat jedoch den Beschwerdeführern eine angemessene Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 2. März 2009 aufgehoben. Die Angelegenheit wird zur materiellen Beurteilung an das Bau- und Justizdepartement des Kantons Solothurn zurückgewiesen. Zur Neuregelung der Kostenfolgen des kantonalen Beschwerdeverfahrens wird die Sache an das Verwaltungsgericht zurückgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Die Einwohnergemeinde Matzendorf hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Einwohnergemeinde Matzendorf, dem Bau- und Justizdepartement sowie dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 3. November 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Haag