Sachverhalt:
A. Die Jules Hagedorn AG betreibt in der Industriezone in Pfäffikon (Gemeinde Freienbach) einen Umschlag- und Aufbereitungsplatz für mineralische Bauabfälle mit einer Behandlungskapazität von jährlich ca. 150'000 Tonnen. Die für den Betrieb zentrale Aufbereitungsanlage steht auf Parzelle Nr. 2941. Zum Betrieb gehört auch ein Umschlagplatz auf den benachbarten Parzellen Nr. 908/3488 unmittelbar neben den Gleisanlagen der Schweizerischen Bundesbahnen (SBB).
B. Am 4. August 1998 forderte das Amt für Umweltschutz des Kantons Schwyz die Jules Hagedorn AG schriftlich auf, ein nachträgliches Baugesuch für ihre Anlagen einzureichen. Das in der Folge eingereichte Gesuch verlangte zur Hauptsache die Beibehaltung des bestehenden Umschlag- und Aufbereitungsplatzes. Ergänzend wurde um Bewilligung für mehrere geplante bauliche Veränderungen auf dem Areal ersucht. So war vorgesehen, den als Grube eingerichteten Umschlagplatz für Gleisaushub (sog. Gosse) am Bahngleis neu zu gestalten. Am 8. Dezember 2000 wurden im kantonalen Amtsblatt sowohl das Baugesuch als auch an anderer Stelle die öffentliche Auflage des Umweltverträglichkeitsberichts zum Baugesuch ausgeschrieben. Aus dem Amtsblatt ging hervor, dass die Einsprachefrist gegen das Baugesuch 20 Tage beträgt. Ebenso wurde darauf hingewiesen, dass Stellungnahmen zum Umweltverträglichkeitsbericht innert 30 Tagen eingereicht werden können.
C. Am 28. Dezember 2000 legten sieben Anwohner gegen das fragliche Baugesuch gemeinsam Einsprache ein. Am 8. Januar 2001 schlossen sich X._ und Y._, die ebenfalls in der Nähe wohnen, der Einsprache an; alle neun Einsprecher gaben gleichzeitig eine Stellungnahme zum aufgelegten Umweltverträglichkeitsbericht ab.
Mit Beschluss vom 8. Januar 2004 wies der Gemeinderat Freienbach die Einsprachen aller Anwohner ab und erteilte die Baubewilligung für die Gesamtanlage mit Nebenbestimmungen. In diesem Beschluss machte er allerdings darauf aufmerksam, dass er Teile der neuen Vorhaben, so auch die Umgestaltung der Gosse auf den Parzellen Nr. 908/3488, bereits vorgängig, aber ohne Mitteilung an die Einsprecher bewilligt habe.
Gegen den kommunalen Entscheid beschwerten sich acht der Einsprecher, darunter X._ und Y._, beim Regierungsrat des Kantons Schwyz. Dieser wies das Rechtsmittel am 28. Juni 2005 ab, soweit er darauf eintrat. Dabei liess er offen, ob auf die Beschwerde von X._ und Y._ einzutreten sei.
D. Sechs der Beschwerdeführer vor dem Regierungsrat fochten seinen Entscheid beim Verwaltungsgericht des Kantons Schwyz an. Im Nachhinein zogen indessen vier Beschwerdeführer ihre Rechtsmittelerklärung zurück, so dass lediglich X._ und Y._ als Beschwerdeführer im verwaltungsgerichtlichen Verfahren übrig blieben. Mit Entscheid vom 17. November 2005 trat das Verwaltungsgericht auf deren Beschwerde nicht ein. Es erwog im Wesentlichen, sie hätten die Einsprache beim Gemeinderat zu spät eingereicht und damit ihre Rechtsmittelbefugnis verwirkt.
E. Gegen den Entscheid des Verwaltungsgerichts führen X._ und Y._ Verwaltungsgerichtsbeschwerde an das Bundesgericht; sie verlangen die Aufhebung des angefochtenen Entscheids. Ausserdem stellen sie den Verfahrensantrag, allfällige Vernehmlassungen der Beschwerdegegner seien ihnen zur Stellungnahme, mindestens jedoch zur Kenntnisnahme zuzustellen.
Die Jules Hagedorn AG und der Regierungsrat beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Verwaltungsgericht ersucht um Abweisung der Beschwerde. Der Gemeinderat Freienbach hat sich nicht vernehmen lassen. Das Bundesamt für Umwelt führt in seinem Schreiben vom 6. September 2006 aus, der angefochtene Entscheid verstosse nicht gegen die eidgenössische Umweltschutzgesetzgebung.
F. Der Präsident der I. öffentlichrechtlichen Abteilung hat der Verwaltungsgerichtsbeschwerde mit Verfügung vom 15. März 2006 aufschiebende Wirkung beigelegt.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Tritt eine kantonale Rechtsmittelinstanz in einer bundesrechtlichen Materie gestützt auf kantonales Verfahrensrecht nicht auf eine Beschwerde ein, so ist ihr Nichteintretensentscheid geeignet, die richtige Anwendung des Bundesrechts zu vereiteln. Die Rüge, das kantonale Verfahrensrecht sei in bundesverfassungswidriger oder bundesrechtswidriger Weise angewendet worden, kann daher in einem solchen Fall mit Verwaltungsgerichtsbeschwerde vorgebracht werden, unabhängig davon, ob zugleich eine Verletzung von materiellem Bundesverwaltungsrecht behauptet wird (<ref-ruling> E. 1a S. 267 mit Hinweisen).
1.2 Die Baubewilligung, die am Ausgangspunkt des vorliegenden Verfahrens steht, betrifft eine Abfallbehandlungsanlage. Diese untersteht der Pflicht zur Umweltverträglichkeitsprüfung (UVP), weil sie eine Behandlungskapazität von mehr als 1000 Tonnen pro Jahr aufweist (Art. 9 Abs. 1 USG [SR 814.01] i.V.m. Art. 1 und Anhang Nr. 40.7 der Verordnung vom 19. Oktober 1988 über die Umweltverträglichkeitsprüfung [UVPV; SR 814.011]).
Eigentlich dreht sich die Auseinandersetzung um die Einhaltung der Umweltschutzvorschriften hinsichtlich der Gesamtanlage. Umstritten ist namentlich die Zulässigkeit der Lärm- und Luftimmissionen sowie der Grundwasserbelastung, die von dieser Anlage ausgehen. Das Verwaltungsgericht hätte insofern Bundesrecht anzuwenden gehabt, wenn es auf die Beschwerde eingetreten wäre.
1.3 Nach dem angefochtenen Entscheid haben die Beschwerdeführer die Einsprachefrist auf der kommunalen Ebene verpasst und deshalb auch die Befugnis zur Erhebung der kantonalen Verwaltungsgerichtsbeschwerde verwirkt. Die Beschwerdeführer halten eine 20-tägige Einsprachefrist bei UVP-pflichtigen Anlagen in allgemeiner Weise für bundesrechtswidrig. Ihrer Meinung nach gebietet das Bundesrecht bei solchen Projekten, dass die Einsprachefrist im kantonalen Verfahren mindestens 30 Tage betragen müsse; diese letztere Frist hätten sie eingehalten. Ausserdem bringen die Beschwerdeführer vor, dass ihnen wegen Mängeln in der Ausschreibung ohnehin keine Einsprachefrist entgegengehalten werden könne. Mit beiden Rügenkomplexen wird eine Verletzung von Bundesrecht geltend gemacht; zum Bundesrecht im Sinne von Art. 104 lit. a OG gehört auch das Bundesverfassungsrecht (vgl. <ref-ruling> E. 2.1 S. 193 mit Hinweisen).
1.4 Keine der in Art. 99-101 OG erwähnten Ausnahmen kommt hier zum Zuge. Namentlich geht es nicht um eine Bau- oder Betriebsbewilligung im Sinne von Art. 99 Abs. 1 lit. e OG; diese Bestimmung betrifft das technische Funktionieren einer Anlage und nicht deren umweltschutzrechtlichen Auswirkungen (<ref-ruling> E. 1a/cc S. 361 f. mit Hinweis). Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, kann auf die Verwaltungsgerichtsbeschwerde eingetreten werden.
1.5 Der rechtserhebliche Sachverhalt ergibt sich mit hinreichender Klarheit aus den Akten. Auf den beantragten Augenschein kann verzichtet werden.
2. In der Beschwerde wird der Verfahrensantrag gestellt, es seien den Beschwerdeführern allfällige Vernehmlassungen der Beschwerdegegner zur Stellungnahme, jedenfalls aber zur Kenntnisnahme zuzustellen.
2.1 Der Anspruch einer Partei, im Rahmen eines Gerichtsverfahrens zu replizieren, bildet einen Teilgehalt des verfassungsmässigen Anspruchs auf rechtliches Gehör (Art. 29 Abs. 2 BV). Im Anwendungsbereich von Art. 6 Ziff. 1 EMRK ist es den Gerichten nicht gestattet, einer Partei das Äusserungsrecht zu eingegangenen Stellungnahmen bzw. Vernehmlassungen der übrigen Verfahrensparteien, unteren Instanzen und weiteren Stellen abzuschneiden. Die Partei ist vom Gericht nicht nur über den Eingang dieser Eingaben zu orientieren; sie muss ausserdem die Möglichkeit zur Replik haben (<ref-ruling> E. 3.3.3 S. 47 mit Hinweisen auf die Rechtsprechung des Europäischen Gerichtshofs für Menschenrechte). Art. 29 Abs. 2 BV gebietet, dass die Gerichte diesen Grundsatz auch ausserhalb von Art. 6 Ziff. 1 EMRK beachten. In diesem Sinne ist festzustellen, dass Art. 29 Abs. 2 BV und Art. 6 Ziff. 1 EMRK im Hinblick auf das Replikrecht in gerichtlichen Verfahren dieselbe Tragweite zukommt. Inwiefern Art. 29 Abs. 2 BV ein Replikrecht auch in Verwaltungsverfahren verleiht, kann hier offen bleiben.
2.2 Gehen in einem Gerichtsverfahren Vernehmlassungen und Stellungnahmen von Parteien und Behörden ein, so werden diese den übrigen Verfahrensbeteiligten im Allgemeinen zur Kenntnisnahme zugestellt. Diese Zustellung kann verbunden werden mit der Anordnung eines zweiten Schriftenwechsels. Ein solcher wird jedoch nur ausnahmsweise eröffnet (vgl. Art. 93 Abs. 3, Art. 110 Abs. 4 OG, neu: Art. 102 Abs. 3 BGG). Ferner kann das Gericht zur Wahrung des rechtlichen Gehörs Eingaben den Verfahrensbeteiligten mit förmlicher Fristansetzung zur freigestellten Vernehmlassung zukommen lassen, was im Bereich des Haftrechts regelmässig der Fall ist. 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.
2.3 Diese Grundsätze sind auch anwendbar auf Fälle, in denen - wie hier - bereits in der Beschwerdeschrift eine Replikmöglichkeit beantragt wird. Insbesondere kann eine neue Eingabe den Verfahrensbeteiligten auch bei dieser Konstellation ohne Fristansetzung zur Kenntnisnahme zugestellt werden.
Im vorliegenden Fall wurden den Beschwerdeführern vom Bundesgericht die Stellungnahmen der Beschwerdegegnerin, des Regierungsrates und des Verwaltungsgerichts sowie die Bemerkungen des Bundesamts für Umwelt am 14. September 2006 zur Kenntnisnahme zugestellt. Damit wurde das Hauptanliegen des Verfahrensantrags erfüllt. Auf diese Zustellung hin haben die Beschwerdeführer nicht reagiert. Unter diesen Umständen ist anzunehmen, sie hätten auf weitere Äusserungen verzichtet; es besteht - nicht zuletzt mit Blick auf das Beschleunigungsgebot - keine Veranlassung, ihnen jetzt noch eine Replikmöglichkeit einzuräumen.
3. Nach § 78 Abs. 1 i.V.m. § 80 Abs. 1 und Abs. 2 des schwyzerischen Planungs- und Baugesetzes vom 14. Mai 1987 (PBG/SZ; SRSZ 400.100) kann innert 20 Tagen ab Veröffentlichung des Baugesuchs bei der Bewilligungsbehörde der Gemeinde Einsprache gegen das Bauvorhaben erhoben werden. Die Beschwerdeführer halten es für bundesrechtswidrig, dass die kantonale Norm bei UVP-pflichtigen Vorhaben eine Einsprachefrist von weniger als 30 Tagen vorsieht.
3.1 Bei kantonal geregelten Einspracheverfahren ist die Festlegung der Einsprachefrist grundsätzlich dem kantonalen Verfahrensrecht überlassen (vgl. Arnold Marti, Kommentar RPG, Zürich 1999, Rz. 31 zu Art. 25a RPG). Zwar sieht Art. 54 Abs. 1 USG vor, dass sich das Beschwerdeverfahren im Anwendungsbereich dieses Erlasses nach VwVG und OG richtet. Daraus lässt sich aber nicht ableiten, dass auch die Einsprachefrist für ein kantonal geregeltes Einspracheverfahren den Vorschriften des VwVG unterstehen würde. Insofern ist es unerheblich, dass Art. 50 VwVG eine Beschwerdefrist von 30 Tagen vorsieht.
3.2 Zu Unrecht behaupten die Beschwerdeführer, eine 20-tägige Frist sei wegen der Komplexität von UVP-pflichtigen Bauprojekten zu kurz, um eine hinreichend begründete Einspracheschrift einreichen zu können. Bestimmt ein Kanton - wie hier - eine derartige Frist für die Erhebung von Einsprachen, so vereitelt er die Durchsetzung des USG nicht. Ebenso wenig verletzt eine derart bemessene Äusserungsfrist den Anspruch auf rechtliches Gehör (Art. 29 Abs. 2 BV).
3.2 Zu Unrecht behaupten die Beschwerdeführer, eine 20-tägige Frist sei wegen der Komplexität von UVP-pflichtigen Bauprojekten zu kurz, um eine hinreichend begründete Einspracheschrift einreichen zu können. Bestimmt ein Kanton - wie hier - eine derartige Frist für die Erhebung von Einsprachen, so vereitelt er die Durchsetzung des USG nicht. Ebenso wenig verletzt eine derart bemessene Äusserungsfrist den Anspruch auf rechtliches Gehör (Art. 29 Abs. 2 BV).
3.3 3.3.1 Nach Art. 15 Abs. 4 UVPV soll der Umweltverträglichkeitsbericht während 30 Tagen einsehbar sein; die Norm behält jedoch abweichende Auflagefristen gemäss dem massgeblichen Verfahren vor. Daher lässt sich aus dieser Bestimmung ohnehin kein Rückschluss auf eine Minimalfrist für die Einsprache ziehen.
3.3.2 Den von Art. 15 Abs. 4 UVPV eingeräumten Spielraum zur Verkürzung der Auflagefrist hat der kantonale Gesetzgeber nicht ausgeschöpft. Vielmehr können im Kanton Schwyz Stellungnahmen zum Umweltverträglichkeitsbericht während der 30-tägigen Auflagefrist abgegeben werden; demgegenüber beträgt die Einsprachefrist auch bei UVP-pflichtigen Bauprojekten nur 20 Tage. Die Koordination wird wie folgt hergestellt: Die beiden Fristen beginnen im selben Zeitpunkt zu laufen (§ 48 Abs. 1 der Vollzugsverordnung vom 3. Juli 2001 zur Kantonalen Verordnung zum Umweltschutzgesetz [USG-VV; SRSZ 711.111]). Die zuständige Behörde leitet sowohl die Einsprachen, die gegen das Projekt eingereicht werden, wie auch die Eingaben zum Umweltverträglichkeitsbericht dem kantonalen Amt für Umweltschutz zur Kenntnisnahme zu (§ 48 Abs. 3 USG-VV).
3.3.3 Art. 15 Abs. 4 UVPV stützt sich auf Art. 9 Abs. 8 USG. Die letztere Norm gewährleistet das Recht der Öffentlichkeit, in den Umweltverträglichkeitsbericht Einsicht zu nehmen, soweit dem nicht überwiegende Geheimhaltungsinteressen entgegenstehen. Art. 9 Abs. 8 USG statuiert hingegen kein allgemeines Einwendungsverfahren (Urteil 1A.226/1996 vom 14. Mai 1997, E. 1a, in: URP 1997 S. 519). Soweit von der Allgemeinheit Stellungnahmen abgegeben werden, handelt es sich bloss um die Ausübung eines Rechtsbehelfs, der keine Parteirechte verleiht. Somit besteht die Einsprache unabhängig davon neben diesem Rechtsbehelf (vgl. Heribert Rausch/Peter M. Keller, in: Kommentar USG, 2. Aufl., Zürich 2001, Rz. 137 zu Art. 9 USG). Vorliegend hat die kommunale Bewilligungsbehörde die Einwendungen aller Einsprecher in ihrem Entscheid berücksichtigt. Musste die Stellungnahme der beiden Beschwerdeführer zum Umweltverträglichkeitsbericht nicht als Einsprache behandelt werden, so war damit ihren Verfahrensansprüchen Genüge getan. Die Beschwerdeführer machen nicht geltend, das kantonale Recht eröffne eine Weiterzugsmöglichkeit für den Fall, dass die Bewilligungsbehörde einer Stellungnahme zum Umweltverträglichkeitsbericht im Ergebnis nicht nachkommt.
3.3.4 Art. 25a Abs. 2 lit. b RPG (SR 700) schreibt eine gemeinsame öffentliche Auflage aller Gesuchsunterlagen vor. Dadurch soll sichergestellt werden, dass nach abgelaufener Auflage- und Äusserungsfrist grundsätzlich alle Einwendungen gegen das Projekt bekannt sind (vgl. die bundesrätliche Botschaft zu Art. 25a RPG, BBl 1994 III 1086). Dem Verwaltungsgericht ist beizupflichten, dass die gebotene Verfahrenskoordination im vorliegenden Zusammenhang mit der beschriebenen Regelung in § 48 Abs. 1 und Abs. 3 USG-VV hinreichend bewerkstelligt werden kann. Deswegen ist es nicht zu beanstanden, dass die Frist für Einsprachen nicht gleich lang dauert wie für Stellungnahmen zum Umweltverträglichkeitsbericht.
3.4 Schliesslich beanspruchen die Beschwerdeführer eine 30-tägige Einsprachefrist auch aufgrund einer analogen Anwendung von Art. 12a NHG (SR 451).
3.4.1 Art. 12a Abs. 1 NHG wurde im Rahmen des Bundesgesetzes vom 18. Juni 1999 über die Koordination und Vereinfachung von Entscheidverfahren (AS 1999 3071) mit einem zweiten Satz ergänzt. Danach dauert die öffentliche Auflage in der Regel 30 Tage. Die dort verankerte Regelfrist bezieht sich unter anderem auf die Bekanntmachung von Projekten, bei denen ein Verbandsbeschwerderecht nach Art. 12 NHG und ein kantonales Einspracheverfahren besteht (vgl. Art. 12a Abs. 1 und Abs. 2 NHG). Art. 55 Abs. 5 USG, worin die Veröffentlichung UVP-pflichtiger Projekte im Hinblick auf ein kantonales Einspracheverfahren geregelt wird, enthält keine Vorschrift, die mit Art. 12a Abs. 1 Satz 2 NHG vergleichbar wäre.
3.4.2 Zu Recht machen die Beschwerdeführer nicht geltend, dass das vorliegende Anlageprojekt sachlich in den Anwendungsbereich von Art. 12 bzw. Art. 12a NHG falle. Von daher ist Art. 12a Abs. 1 Satz 2 NHG im vorliegenden Fall nicht anwendbar. Die Rechtsnatur dieser Bestimmung kann hier offen bleiben. Jedenfalls lässt sich nicht im Sinne einer analogen Auslegung in Art. 55 Abs. 5 USG hineininterpretieren, dass dort eine verbindliche Fristvorgabe von 30 Tagen für das kantonale Einspracheverfahren enthalten sein soll (a.M. Theo Loretan, in: Kommentar USG, 2. Aufl. 2002, Rz. 45 zu Art. 55 USG).
3.5 Zusammengefasst ist es weder bundesverfassungs- noch bundesrechtswidrig, wenn kantonal eine Einsprachefrist von 20 Tagen beim betroffenen UVP-pflichtigen Projekt gilt. Daran ändert der Umstand nichts, dass das kantonale Recht parallel dazu Stellungnahmen gegen den Umweltverträglichkeitsbericht während einer 30-tägigen Frist zulässt.
4. Weiter bringen die Beschwerdeführer vor, ihre Einsprache sei auch deshalb nicht verspätet, weil das Anlageprojekt mangelhaft ausgeschrieben worden sei. Wurden die Mindestanforderungen an die Publikation UVP-pflichtiger Projekte vorliegend verletzt, so darf den Beschwerdeführern daraus kein Nachteil erwachsen (vgl. Urteil 1A.136/2004 vom 5. November 2004, E. 3.3 in: URP 2005 S. 1).
4.1 Aus den beiden Ausschreibungen im Amtsblatt ging die Unterscheidung zwischen den Fristen für Einsprachen und Stellungnahmen zum Umweltverträglichkeitsbericht klar hervor. Da sich die 30-tägige Frist nur auf allfällige Stellungnahmen zum Umweltverträglichkeitsbericht bezog, durften die Beschwerdeführer daraus nach Treu und Glauben nicht auch eine entsprechend lange Einsprachefrist ableiten. Nicht nachvollziehbar ist es im Übrigen, wenn die Beschwerdeführer dem Verwaltungsgericht im Zusammenhang mit dem Inhalt der beiden Publikationen eine unvollständige Sachverhaltsermittlung vorwerfen. Es trifft nicht zu, dass im angefochtenen Entscheid die von den Beschwerdeführern angeführten Einzelheiten in der Publikation zur Auflage des Umweltverträglichkeitsberichts übersehen worden sind. Ebenso wenig legen die Beschwerdeführer dar, inwiefern sich diese Einzelheiten auf die Frage des Fristenlaufs auswirken sollen.
4.2 Die Beschwerdeführer kritisieren, in der Ausschreibung sei nicht ausdrücklich auf die geplante Neugestaltung der Gosse hingewiesen worden. Nach dem Verwaltungsgericht war dieses Teilvorhaben in der Ausschreibung des Baugesuchs mitenthalten und damit hinreichend veröffentlicht worden. Mit dieser Würdigung hat es weder den Sachverhalt unrichtig festgestellt noch Bundesrecht verletzt.
Die Umschreibung des Bauobjekts im Amtsblatt war genügend weit gefasst, indem das Vorhaben als "Umschlag- und Aufbereitungsplatz für mineralische Bauabfälle" bezeichnet wurde. Die Gosse bildet ja einen Teil des Umschlagplatzes. Die Ausschreibung enthielt die Koordinaten und die Adresse der Gesamtanlage. Zwar ist es richtig, dass im Amtsblatt lediglich die Hauptparzelle Nr. 2941 und nicht auch die Parzellen, auf denen sich die Gosse befindet, genannt wurden. Darauf kommt es aber hier wiederum nicht an. Die Stossrichtung der Einsprache vom 8. Januar 2001 wendete sich vor allem gegen die Immissionen der Aufbereitungsanlage; die Abfallanlieferung durch die SBB, in deren Rahmen die Gosse genutzt wird, wurde beiläufig angesprochen. Im Übrigen bestreiten die Beschwerdeführer die Feststellung des Verwaltungsgerichts nicht, wonach die aufgelegten Baugesuchsunterlagen auf die neuen Anlageteile und insbesondere auf die Gosse Bezug nahmen. Es lässt sich daher nicht annehmen, die unvollständige Bezeichnung der betroffenen Parzellen in der Ausschreibung habe die Beschwerdeführer von einer rechtzeitigen Einsprache abgehalten.
4.3 Die von der Gemeinde - vorzeitig - bewilligte Gosse ist unbestreitbar nicht deckungsgleich zum entsprechenden Vorhaben im ursprünglichen Baugesuch. Im angefochtenen Entscheid geht das Verwaltungsgericht indessen davon aus, die diesbezügliche Projektänderung sei von untergeordneter Bedeutung gewesen. Diese Annahme erweist sich nicht als offensichtlich unrichtig. Die Beschwerdeführer zeigen denn auch nicht auf, inwiefern die fragliche Projektänderung in umweltrelevanter Sicht erheblich sein soll. Die insgesamt UVP-pflichtige Anlage musste somit wegen dieser Projektänderung nicht nochmals ausgeschrieben werden (vgl. Loretan, a.a.O., Rz. 46 zu Art. 55 USG). Da die Beschwerdeführer nicht rechtzeitig innerhalb der 20-tägigen Einsprachefrist reagiert haben, können sie sich auch nicht gegen die Projektänderung wehren.
4.4 Die Gemeinde hat Teile der neuen Vorhaben der Beschwerdegegnerin, so auch die Gosse, vorzeitig bewilligt und die Einsprecher erst nachträglich, anlässlich der Bewilligung vom 8. Januar 2004 für die Gesamtanlage, darüber informiert. Es wurde bereits dargelegt, dass die bewilligte Gosse nicht wesentlich von der aufgelegten Variante abweicht (E. 4.3). Bezüglich der übrigen vorzeitig bewilligten Projektteile wird von den Beschwerdeführern nicht angezweifelt, dass es sich um Bestandteile des Gesamtprojekts gemäss dem ursprünglichen Baugesuch handelte. Da all diese Teilvorhaben Gegenstand der ursprünglichen Ausschreibung waren, führt die mangelhafte Eröffnung der Teilbewilligungen ebenfalls nicht dazu, dass es insofern auf das Verpassen der Einsprachefrist nicht mehr ankommen dürfte.
5. Nach dem Gesagten ist die Beschwerde abzuweisen. Bei diesem Ausgang tragen die Beschwerdeführer die Gerichtskosten (Art. 156 Abs. 1 und Abs. 7 OG). Sie haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 159 Abs. 2 und Abs. 5 OG).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 3'000.-- wird den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren, unter solidarischer Haftbarkeit, gesamthaft mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Gemeinderat Freienbach, dem Regierungsrat und dem Verwaltungsgericht des Kantons Schwyz, Kammer III, sowie dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 14. Dezember 2006
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: