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.