Sachverhalt:
A. Am 13. November 1978 hatte der Regierungsrat des Kantons Schwyz den Sanierungsplan für die Kiesgrube Y._ Nuolen/Wangen-Tuggen unter diversen Auflagen genehmigt. Auch der Abbau- und Sanierungsplan für die Kiesgewinnung Rütihof wurde am 19. Mai 1981 genehmigt. Der Abschluss der Abbau- und Auffüllungsarbeiten war per Ende 1999 vorgesehen.
Am 25. Februar 1999 stellte die Y._ AG als Betreiberin bei den Gemeinderäten Tuggen und Wangen das Gesuch um Verlängerung der vorerwähnten Bewilligungen. Gegen das Vorhaben gingen bei beiden Gemeinderäten Einsprachen ein, darunter auch diejenige der Eheleute X._.
B. Nach langwierigen ergebnislosen Verfahren schlossen der Gemeinderat Wangen, der Gemeinderat Tuggen und die Y._ AG am 22./25. August 2008 einen öffentlich-rechtlichen Vertrag ab. Daraufhin zog der Rechtsvertreter der Einsprecher die im Jahr 1999 erhobene Einsprache mit Schreiben vom 12. September 2008 mit der Begründung zurück, der öffentlich-rechtliche Vertrag nehme die hauptsächlichen Anliegen der Einsprecher auf, weshalb der Zweck der Einsprache erfüllt sei. Eine weitere Aufrechterhaltung würde lediglich verfahrenstechnische Fragen aufwerfen, welche eine baldige Erledigung verzögern würden. Über diesen Rückzug informierte der Rechtsanwalt seine Mandanten mit Schreiben vom 15. September 2008. Tags darauf teilten die Eheleute X._ sowohl ihrem Vertreter als auch dem Gemeinderat Wangen mit, dass sie dem Anwalt das Mandat per sofort entzögen und an der Einsprache weiterhin festhielten.
C. Mit Beschluss vom 25. September 2008 widerrief der Gemeinderat Tuggen seinen anders lautenden Beschluss vom 2. Februar 2006 und erteilte der Y._ AG die Abbaubewilligung unter Auflagen und Bedingungen. Auch der Gemeinderat Wangen widerrief gleichentags einen Beschluss vom 26. Januar 2006 und verlängerte die Bewilligungen für den Abbau-, Sanierungs- und Rekultivierungsplan der Kiesgruben "Rütihof" und "Bachtellen" der Gemeinde Wagen im bisherigen Rahmen. Zudem ersuchte er den Regierungsrat um Abschreibung des hängigen Beschwerdeverfahrens. In Dispositiv-Ziffer 5 hielt er schliesslich fest, dass die Einsprachen infolge Rückzugs als gegenstandslos geworden abgeschrieben würden.
D. Gegen den Beschluss des Gemeinderats Wangen vom 25. September 2008 gelangten die Eheleute X._ an den Regierungsrat des Kantons Schwyz. Neben der Aufhebung des Beschlusses verlangten sie, der Gemeinderat Wangen sei zu verpflichten, sie über den vollen Wortlaut des öffentlich-rechtlichen Vertrags zwischen der Y._ AG und den betroffenen Gemeinderäten in Kenntnis zu setzen.
Der Regierungsrat trat mit Beschluss vom 9. Juni 2009 auf die Beschwerde nicht ein.
E. Im daraufhin angestrengten Verfahren vor dem kantonalen Verwaltungsgericht räumte Letzteres dem früheren Rechtsanwalt der Beschwerdeführer als Beigeladenem ebenfalls die Möglichkeit zur Stellungnahme ein, wovon dieser am 9. Juli 2009 auch Gebrauch machte. Mit Urteil vom 19. November 2009 wies das Verwaltungsgericht die Beschwerde ab.
F. Die Eheleute X._ beantragen dem Bundesgericht am 12. Januar 2010 mit Beschwerde in öffentlich-rechtlichen Angelegenheiten die Aufhebung des vorinstanzlichen Urteils. Weiter sei der Regierungsrat des Kantons Schwyz zu verpflichten, auf die Beschwerde materiell einzutreten und den Beschwerdeführern das rechtliche Gehör zu gewähren. Neben einer Verletzung des rechtlichen Gehörs machen die Beschwerdeführer materielle Rechtsverletzungen im Zusammenhang mit der vorinstanzlichen Würdigung des Einspracherückzugs geltend.
Die Y._ AG als private Beschwerdegegnerin und der Gemeinderat Wangen schliessen je auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Desgleichen beantragen der Regierungsrat und das Verwaltungsgericht des Kantons Schwyz (sinngemäss), die Beschwerde sei abzuweisen.
Im zweiten Schriftenwechsel halten die Beteiligten an ihren Anträgen fest.

Erwägungen:
1. Das angefochtene Urteil des Verwaltungsgerichts unterliegt grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>). Dadurch, dass das Verwaltungsgericht den Nichteintretensentscheid des Regierungsrats geschützt hat, ist der Rechtsmittelrückzug im kantonalen Verfahren als rechtsgültig erkannt und eine weitere Beschwerdemöglichkeit der Beschwerdeführer im kantonalen Verfahren verneint worden. Letztere sind durch den angefochtenen Entscheid besonders berührt und haben ein schützenswertes Interesse an dessen Aufhebung (<ref-law>). Auf die frist- und formgerecht eingereichte Beschwerde ist - unter Vorbehalt einer rechtsgenüglichen Begründung - einzutreten.
2. Die Beschwerdeführer werfen den kantonalen Instanzen eine Gehörsverletzung vor: Einerseits habe das Verwaltungsgericht nur auf die jüngere Sachverhaltsdarstellung des früheren Vertreters abgestellt, ohne die anderslautenden Ausführungen der Beschwerde zu würdigen. Ausserdem sei ihnen die Möglichkeit zur Stellungnahme verwehrt geblieben.
2.1 Gemäss <ref-law> steht den Parteien das rechtliche Gehör zu. Dieser Anspruch ist formeller Natur, womit seine Verletzung ungeachtet der materiellen Begründetheit des Rechtsmittels zur Gutheissung der Beschwerde und zur Aufhebung des angefochtenen Entscheids führt (statt vieler: <ref-ruling> E. 2.2 E. S. 190). Das rechtliche Gehör dient einerseits der Klärung des Sachverhalts, anderseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht der betroffenen Person, sich vor Erlass eines ihn belastenden Entscheids zur Sache, jedenfalls zumindest zum Beweisergebnis äussern zu können, wenn dieses geeignet ist, den Ausgang des Verfahrens zu beeinflussen (<ref-ruling> E. 2b S. 56).
2.2 Vorab ist festzuhalten, dass eine von der Auffassung der Beschwerdeführer abweichende rechtliche Würdigung durch das Verwaltungsgericht nicht automatisch eine Verletzung des rechtlichen Gehörs bedeutet. Gelangt die Vorinstanz in willkürfreier Berücksichtigung sämtlicher relevanter Gesichtspunkte zu einer anderen Schlussfolge als die Beschwerdeführer, ist ihr daraus kein Vorwurf zu machen. Dies scheinen die Beschwerdeführer zu verkennen.
2.3 Das Verwaltungsgericht hat das Rückzugsschreiben des Anwalts vom 12. September 2008 an die Gemeinde, den Brief an seine Mandanten vom 15. September 2008 und schliesslich seine Stellungnahme im verwaltungsgerichtlichen Verfahren vom 9. Juli 2009 beigezogen. Letztere ist den Beschwerdeführern zur Kenntnisnahme zugestellt worden. Wie das Bundesgericht in <ref-ruling> E. 2.2 S. 99 zur eigenen Praxis festgehalten hat, wird ein zweiter Schriftenwechsel nur ausnahmsweise eröffnet. Das Gericht kann ferner zur Wahrung des rechtlichen Gehörs Eingaben den Verfahrensbeteiligten mit förmlicher Fristansetzung zur freigestellten Vernehmlassung zukommen lassen. Schliesslich wird eine neu eingegangene Eingabe den Parteien häufig ohne ausdrücklichen Hinweis auf allfällige weitere Äusserungsmöglichkeiten zur (blossen) Kenntnisnahme übermittelt. Kommen Verfahrensbeteiligte, welche eine solche Eingabe ohne Fristansetzung erhalten haben, zum Schluss, sie möchten nochmals zur Sache Stellung nehmen, so sollen sie dies aus Gründen des Zeitgewinns tun, ohne vorher darum nachzusuchen. Nach Treu und Glauben hat dies jedoch umgehend zu erfolgen. Das Bundesgericht wartet bei der letztgenannten Vorgehensweise mit der Entscheidfällung zu, bis es annehmen darf, der Adressat habe auf eine weitere Eingabe verzichtet.
Ebenso verhält es sich im vorliegenden Fall. Die Beschwerdeführer haben in keiner Weise auf die Stellungnahme des früheren Rechtsvertreters reagiert. Weder haben sie sich direkt dazu geäussert, noch haben sie eine neue Fristansetzung zur Replikmöglichkeit verlangt. Das Verwaltungsgericht war nicht gehalten, nochmals förmlich nachzufragen, ob ein weiterer Schriftenwechsel gewünscht sei. Hinzu kommt, dass im fraglichen Schreiben keine neuen rechtserheblichen Tatsachen geltend gemacht wurden. Der ehemalige Rechtsvertreter hat in seiner Stellungnahme lediglich nochmals deutlich gemacht, dass er zwar keine Kopie des Vertrags erhalten hatte, jedoch ohne die nötigen Informationen zum Vertragsinhalt die wichtigsten Punkte sowohl beim Rückzug als auch beim Schreiben an die Einsprecher gar nicht hätte erwähnen können.
2.4 Auch dem Gemeinderat Wangen ist nicht vorzuwerfen, dass er den Beschwerdeführern den öffentlich-rechtlichen Vertrag zwischen den Gemeinden und der privaten Beschwerdegegnerin nach der Rückzugserklärung des Anwalts nicht mehr zugestellt hat. Wie nachfolgend zu zeigen sein wird, durfte die Gemeinde den Rückzug als rechtsgültig einschätzen, weshalb kein Grund mehr bestand, nach abgeschlossenem Verfahren weitere Akteneinsicht zu gewähren. Selbst wenn ein solcher Anspruch noch bestanden hätte, wäre eine etwaige Gehörsverletzung im Verfahren vor dem Regierungsrat geheilt worden, hat der Regierungsrat gemäss § 46 der kantonalen Verordnung über die Verwaltungsrechtspflege vom 6. Juni 1974 (VRP/SZ; SRSZ 234.110) doch grundsätzlich umfassende, freie Überprüfungsbefugnis und konnten die Beschwerdeführer das gesamte Vertragswerk inzwischen einsehen.
2.5 Soweit die Beschwerdeführer den kantonalen Behörden Befangenheit und Willkür im Verfahren zum Vorwurf machen, genügt die Beschwerde den Begründungsanforderungen nicht (<ref-law>). Einzig aus dem Umstand, dass ihre Rechtsbegehren nicht ihren Vorstellungen entsprechend beurteilt wurden, können die Beschwerdeführer keine derartigen Verfahrensmängel ableiten. Die Rechtsauskunft des Sicherheitsdepartements an die Gemeinde Wangen erging vor dem Rückzug des Rechtsmittels und zeigte etwaige verfahrensrechtliche Problematiken auf. Die Gemeinde hatte angefragt, ob die Einsprachen aufgrund des öffentlich-rechtlichen Vertrags vom 22./25. August 2008 gegenstandslos werden könnten. Mit dem Rückzug wurden die Erwägungen des Departements hinfällig. Es ist nicht ersichtlich und wurde auch nicht rechtsgenüglich dargetan, weshalb dieser Sachverhalt Anlass zu aufsichtsrechtlichen Schritten hätte geben sollen.
3. Weiter machen die Beschwerdeführer geltend, das Verwaltungsgericht stütze seine Argumentation auf rechts- und tatsachenwidrige Annahmen. Ihrer Meinung nach hatte der damalige Anwalt keine Kenntnis vom Vertragsinhalt, weshalb der Rückzug mit Willensmängeln behaftet gewesen sei. Zudem habe die Gemeinde gewusst, dass der Rechtsvertreter von der Gegenseite Fr. 12'000.-- in Aussicht gestellt bekommen habe. Sie habe wissen müssen, dass diese Abmachung nicht zulässig gewesen sei. Zudem sei lebensfremd, dass 30 Einsprecher gleichzeitig und sofort mit dem Einspracherückzug einverstanden seien. Das Verwaltungsgericht blende dies aus.
3.1 Zieht eine Partei ein Rechtsmittel zurück, so bringt sie damit das Verfahren zum Abschluss. Dies gilt auch im Verwaltungsrechtspflegeverfahren; gestützt auf eine Rückzugs- bzw. Abstandserklärung erklärt die zuständige Behörde das Verfahren für erledigt bzw. schreibt sie es (vom Protokoll) ab (Fritz Gygi, Bundesverwaltungsrechtspflege, 2. Aufl., Bern 1983, S. 325 ff.; ALFRED KÖLZ/ISABELLE HÄNER, Verwaltungsverfahren und Verwaltungsrechtspflege des Bundes, 2. Aufl., Zürich 1998, S. 242 f., Rz. 682 und 683; ANDRÉ GRISEL, Traité de droit administratif, Neuchâtel 1984, S. 937). Der - ausdrücklich und vorbehaltlos bzw. bedingungslos erklärte - Rückzug der Beschwerde bedeutet Verzicht auf die Überprüfung des Rechtsbegehrens mit der Folge, dass die Gegenstand der Beschwerde bildende Verfügung rechtskräftig wird (KÖLZ/HÄNER, a.a.O., Rz. 683). Es verhält sich nach dem Rückzug und nach der Abschreibung der Beschwerde so, als wäre sie nicht erhoben worden (vgl. WALTER KÄLIN, Das Verfahren der staatsrechtlichen Beschwerde, 2. Aufl. Bern 1994, S. 394 oben). Der bedingungslos erklärte Rückzug ist grundsätzlich endgültig, d.h. nicht widerrufbar; vorbehalten bleiben der Vertrauensschutz oder Willensmängel (<ref-ruling> E. 3 S. 237 f.; Urteil 2A.396/2005 des Bundesgerichts vom 22. Juni 2005 mit zahlreichen Hinweisen zur Literatur).
3.2 Die Beschwerdeführer anerkennen die grundsätzlichen Rechtsfolgen eines Einspracherückzugs, beharren aber auf ihrer Darstellung, wonach der Rechtsanwalt keine Kenntnis vom Vertragsinhalt gehabt habe. Deshalb habe er die Einsprache nicht rechtsgültig zurückziehen können. Der von der Vorinstanz aus dem Schreiben vom 12. September 2008 gezogene Schluss, dass der Anwalt in Kenntnis der Sach- und Rechtslage - und damit offenbar auch mit Wissen um den Inhalt des öffentlich-rechtlichen Vertrags - gehandelt habe, beruht auf der Beweiswürdigung des Verwaltungsgerichts. Dass diese geradezu willkürlich wäre, wird nicht dargetan. Im Gegenteil, sie scheint durchaus nachvollziehbar, nimmt der Anwalt im Rückzugsschreiben vom 12. September 2008 doch Bezug auf die strittigen Einsprachepunkte, welche durch die gefundene Lösung hinfällig würden. So erläutert er, die hauptsächlichen Anliegen der Einsprecher würden im Vertrag aufgenommen: Es würden keine neuen Abbaugebiete durch das Dorf Nuolen hindurch erschlossen (schon gar nicht für Abbauvorhaben auf Tuggner Gemeindegebiet), und es erfolge weiterhin ein zumindest anteilsmässiger Transport auf dem Seeweg; es gelte ein verbindlicher Zeitplan für den verbleibenden Abbau und die nötigen Rekultivierungen mit einem Abschluss spätestens im Jahr 2020; zudem würden etwa übliche Betriebszeiten vorgeschrieben. Mit diesem Verhandlungsergebnis würden die zentralsten Punkte der Einsprache vom 6. Mai 1999 aufgenommen. Damit habe die damalige Einsprache ihren Zweck bestmöglich erfüllt und eine weitere Aufrechterhaltung würde lediglich verfahrenstechnische Fragen aufwerfen, welche eine baldige Erledigung verzögern würden. Aus den angeführten Gründen werde die öffentlich-rechtliche Einsprache vom 6. Mai 1999 zurückgezogen. Diese Details hätte der Anwalt ohne Kenntnis der für die Einsprecher massgeblichen Vertragsstellen gar nicht nennen können. Nichts anderes geht aus dem Brief an die damaligen Mandanten vom 15. September 2008 hervor. Der Rechtsvertreter nennt die soeben zitierten Punkte und führt ergänzend aus, er habe ein Arrangement über seine Aufwände treffen können, sodass die Einsprecher nicht mit weiteren Kosten zu rechnen hätten. Eine Woche später verweist er die heutigen Beschwerdeführer, was den Inhalt des Vertrags anbelangt, auf die in den Lokalzeitungen veröffentlichten Berichte und meint: "Mehr weiss ich dazu auch nicht". Dem Verwaltungsgericht ist nicht vorzuwerfen, dass es aufgrund dieser Ausgangslage von einem genügenden Wissensstand des Rechtsvertreters ausging.
3.3 Aber selbst wenn der Anwalt ohne ausreichende Kenntnis der Sach- und Rechtslage gehandelt hätte, wäre ihm zwar eine Verletzung der Sorgfaltspflicht vorzuwerfen. Darin läge aber kein Willensmangel. Willensmängel bei Prozesserklärungen wie beim strittigen Rechtsmittelrückzug können - in Anlehnung an die Willensmängelgrundsätze im OR - darin bestehen, dass jemand getäuscht (<ref-law>) oder bedroht (<ref-law>) wurde oder sich in einem wesentlichen Irrtum befand (<ref-law>; GYGI, a.a.O., S. 59). Dafür liegen keine Anhaltspunkte vor bzw. wurden keine solchen geltend gemacht.
3.4 Demnach war kein Willensmangel beim Einspracherückzug zu erkennen. Der Anwalt war am 12. September 2008 im Besitz einer gültigen Prozessvollmacht. Für die Gemeinde Wangen drängten sich zu Recht keine Zweifel an der Rechtmässigkeit des Rückzugs auf. Daran ändert nichts, dass die Beschwerdeführer umgehend an die Gemeinde gelangt sind und unter Berufung auf den Mandatsentzug ihr Rechtsmittel aufrechterhalten wollten. Das interne Verhältnis zwischen Anwalt und Mandanten war für das Verwaltungs(gerichts)-Verfahren irrelevant. Die Rügen der Beschwerdeführer sind unbehelflich.
4. Demzufolge ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend, sind die Gerichtskosten den Beschwerdeführern aufzuerlegen (<ref-law>). Die Beschwerdeführer haben die private Beschwerdegegnerin zudem angemessen für das bundesgerichtliche Verfahren zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben die private Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Gemeinderat Wangen sowie dem Regierungsrat und dem Verwaltungsgericht des Kantons Schwyz, Kammer III, schriftlich mitgeteilt.
Lausanne, 17. September 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Scherrer Reber