Sachverhalt: A. Die zum AMCOR-Konzern gehörende Poly Laupen AG ist im Druckereigewerbe tätig und spezialisiert auf die Herstellung von Verpackungen und Werbematerialien. Seit einiger Zeit verfügt sie über Bewilligungen für Nachtarbeit sowie vorübergehende Sonntagsarbeit. Am 30. April 2002 wurde im Bundesblatt ein Gesuch der Poly Laupen AG um Nachtarbeit sowie um regelmässig wiederkehrende Sonntagsarbeit publiziert. Mit individuell eröffneter Verfügung vom 4. Juni 2002, die bereits am 28. Mai 2002 im Bundesblatt veröffentlicht worden war, erteilte das Staatssekretariat für Wirtschaft (seco) der Poly Laupen AG die Bewilligung für Nachtarbeit sowie für regelmässig wiederkehrende Sonntagsarbeit im Betriebsteil "Bogenoffset- und Rollentiefdruckanlagen, Stanz-, Präge- und Klebmaschinen in der Abteilung Kartonage" für bis zu 20 Männern oder Frauen pro Schicht und an maximal 20 Sonn- und Feiertagen für die Dauer vom 15. April 2002 bis zum 19. April 2003. Zur Begründung gab das seco in der Verfügung "wirtschaftlich unentbehrliche Betriebsweise" an. B. Gegen diese Verfügung reichte die Mediengewerkschaft comedia am 3. Juni 2002 bei der Rekurskommission des Eidgenössischen Volkswirtschaftsdepartements (nachfolgend: Rekurskommission EVD) Beschwerde ein mit dem sinngemässen Antrag auf Aufhebung der Bewilligung für Sonntagsarbeit. In der Folge führte die Rekurskommission EVD einen mehrfachen Schriftenwechsel durch. Dabei verlagerte sich die Diskussion nach dem zweiten Schriftenwechsel gegenüber der Begründung der Sonntagsarbeit durch das seco auf eine alternative Rechtfertigung derselben. In diesem Zusammenhang unterbreitete die Rekurskommission EVD sowohl dem seco als auch der Poly Laupen AG einen Katalog mit konkreten Fragen zur Sachlage. Zu den Antworten konnten die Verfahrensbeteiligten Stellung nehmen. Mit Beschwerdeentscheid vom 2. Juni 2004 wies die Rekurskommission EVD die bei ihr hängige Beschwerde der comedia ab und auferlegte dieser die Verfahrenskosten im Betrag von Fr. 1'447.20 sowie eine Parteientschädigung zugunsten der Poly Laupen AG im Umfang von Fr. 5'000.-- (inkl. Mehrwertsteuer). C. Die Mediengewerkschaft comedia führt Verwaltungsgerichtsbeschwerde beim Bundesgericht mit dem Antrag, der Beschwerdeentscheid der Rekurskommission EVD vom 2. Juni 2004 sei aufzuheben, und die Sache sei zu neuem Entscheid an die Rekurskommission zurückzuweisen. In ihrer Beschwerdebegründung beanstandet sie verschiedene formelle Mängel und macht in der Sache geltend, der gesetzlich erforderliche Nachweis der wirtschaftlichen Unentbehrlichkeit der Sonntagsarbeit sei nicht erbracht. Die Poly Laupen AG und das seco schliessen auf Abweisung der Beschwerde. Die Rekurskommission EVD hat auf eine Stellungnahme verzichtet.