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.

Das Bundesgericht zieht in Erwägung:
1. Gegen den angefochtenen Entscheid kann in Anwendung von Art. 97 ff. OG Verwaltungsgerichtsbeschwerde beim Bundesgericht geführt werden. Die Beschwerdeführerin ist als zuständige Gewerkschaft im Verpackungssektor zur Beschwerde berechtigt (Art. 103 lit. c OG i.V.m. Art. 58 Abs. 1 des Bundesgesetzes vom 13. März 1964 über die Arbeit in Industrie, Gewerbe und Handel [Arbeitsgesetz, ArG; SR 822.11]), ohne dass es darauf ankommt, ob direkt betroffene Arbeitnehmer zu den Mitgliedern des Verbandes gehören (<ref-ruling> E. 1a S. 271). Auf das Erfordernis des aktuellen Interesses kann - wie dies bereits die Vorinstanz getan hat - verzichtet werden, da die aufgeworfenen Fragen angesichts der jeweils bloss zeitlich begrenzten Gültigkeit der umstrittenen Bewilligung sonst nie (höchst)richterlich geklärt werden könnten (vgl. <ref-ruling> E. 1b S. 36, mit Hinweisen). Streitgegenstand ist nur die Bewilligung der Sonntagsarbeit; nicht angefochten ist die ebenfalls erteilte Bewilligung für Nachtarbeit. Diese Eintretensvoraussetzungen sind im Übrigen unter den Verfahrensbeteiligten nicht umstritten.
2. Gemäss <ref-law> ist in der Zeit zwischen Samstag 23 Uhr und Sonntag 23 Uhr die Beschäftigung von Arbeitnehmern unter Vorbehalt von <ref-law> untersagt. Nach dieser Bestimmung bedürfen Ausnahmen vom Verbot der Sonntagsarbeit der Bewilligung (Abs. 1). Dauernde oder regelmässig wiederkehrende Sonntagsarbeit wird bewilligt, sofern sie aus technischen oder wirtschaftlichen Gründen unentbehrlich ist (Abs. 2). Art. 28 der bundesrätlichen Verordnung 1 vom 10. Mai 2000 zum Arbeitsgesetz (ArGV 1; SR 822.111) konkretisiert die Unentbehrlichkeit der Sonntagsarbeit. Danach liegt wirtschaftliche Unentbehrlichkeit insbesondere dann vor, wenn das angewandte Arbeitsverfahren mit unvermeidlich hohen Investitionen verbunden ist, die ohne Sonntagsarbeit nicht amortisiert werden können (Art. 28 Abs. 2 lit. b ArGV 1), oder wenn die Konkurrenzfähigkeit gegenüber Ländern mit vergleichbarem sozialem Standard wegen längerer Arbeitszeiten oder anderer Arbeitsbedingungen im Ausland erheblich beeinträchtigt ist und durch die Bewilligung die Beschäftigung mit grosser Wahrscheinlichkeit gesichert wird (Art. 28 Abs. 2 lit. c ArGV 1). In keinem Fall darf der Arbeitgeber den Arbeitnehmer ohne dessen Einverständnis zu Sonntagsarbeit heranziehen (<ref-law>).
3. 3.1 Die Beschwerdegegnerin begründete ihr ursprüngliches Gesuch um Bewilligung von Sonntagsarbeit pauschal mit "wirtschaftlicher und technischer Unentbehrlichkeit"; eine Gesetzes- oder Verordnungsbestimmung nannte sie dazu nicht, machte im Gesuchsformular allerdings namentlich gewisse allgemeine Angaben zur Amortisierbarkeit ihrer Anlagen sowie zur Konkurrenzsituation mit dem Ausland. Das seco erteilte nach Vornahme ergänzender Abklärungen die Bewilligung einzig und ohne nähere Ausführungen mit der Begründung "wirtschaftlich unentbehrliche Betriebsweise". Die vom seco vorgenommenen Abklärungen waren auf eine Prüfung der mit dem angewandten Arbeitsverfahren verbundenen Investitionskosten ausgerichtet. Im Beschwerdeverfahren diskutierten die Verfahrensbeteiligten denn auch zunächst vorwiegend die Frage, ob die Voraussetzungen von Art. 28 Abs. 2 lit. b ArGV 1 erfüllt seien. Erst in der Duplik berief sich die Beschwerdegegnerin auch ausdrücklich auf den Ausnahmetatbestand von Art. 28 Abs. 2 lit. c ArGV 1, machte also alternativ die Konkurrenzfähigkeit mit ausländischen Betrieben geltend. Die Vorinstanz nahm dazu weitere Abklärungen vor und begründete schliesslich ihren Entscheid einzig mit Art. 28 Abs. 2 lit. c ArGV 1, wobei sie ausdrücklich offen liess, ob auch die Voraussetzungen von Art. 28 Abs. 2 lit. b ArGV 1 erfüllt wären.
3.2 Die Beschwerdeführerin sieht im Vorgehen der Vorinstanz eine unzulässige Ausweitung des Streitgegenstandes und eine Verletzung von <ref-law>. Nach dieser Bestimmung können verspätete Parteivorbringen, die ausschlaggebend erscheinen, trotz der Verspätung berücksichtigt werden. Sie bleiben aber auf den Streitgegenstand beschränkt. Im Verfahren der nachträglichen Verwaltungsrechtspflege ist Streitgegenstand das Rechtsverhältnis, das Gegenstand der angefochtenen Verfügung bildet, soweit es im Streit liegt. Beschwerdebegehren, die neue, in der angefochtenen Verfügung nicht geregelte Fragen aufwerfen, sind unzulässig (René Rhinow/Heinrich Koller/Christina Kiss, Öffentliches Prozessrecht und Justizverfassungsrecht des Bundes, Basel/Frankfurt a.M. 1996, Rz. 901 und 1220). In einem Rechtsmittelverfahren vor oberer Instanz kann der Streitgegenstand grundsätzlich nur eingeschränkt, jedoch nicht mehr erweitert werden (<ref-ruling> E. 2.2 S. 536; André Moser, in: Moser/Uebersax, Prozessieren vor eidgenössischen Rekurskommissionen, Basel/Frankfurt a.M. 1998, Rz. 2.13).
3.3 Streitgegenstand ist im vorliegenden Fall die Bewilligung von (regelmässig wiederkehrender) Sonntagsarbeit an maximal 20 Sonn- und Feiertagen, wie sie vom seco als Bewilligungsbehörde erteilt wurde. Dass diese Bewilligung unter verschiedenen Voraussetzungen gewährt werden kann, schränkt den Streitgegenstand nicht ein. Die rechtliche Wirkung, nicht die Begründung oder Herleitung definiert den Streitgegenstand, auch wenn unter Umständen auf die Begründung zurückgegriffen werden muss, um die Rechtsfolge zu verstehen. Bereits das Arbeitsgesetz nennt verschiedene Konstellationen, bei denen regelmässig wiederkehrende Sonntagsarbeit zulässig ist. Das Verordnungsrecht konkretisiert die entsprechenden Voraussetzungen und schafft dabei weitere Kategorien. Die Rechtsfolge bleibt aber immer dieselbe, nämlich die Bewilligung regelmässig wiederkehrender Sonntagsarbeit.
Die Vorinstanz ging im angefochtenen Entscheid nicht über die vom seco festgelegte Rechtsfolge hinaus. Zwar stützte sie ihren Entscheid auf den Ausnahmetatbestand von Art. 28 Abs. 2 lit. c ArGV 1, wäh renddem sich die Bewilligungsbehörde auf die Prüfung der Voraussetzungen von Art. 28 Abs. 2 lit. b ArGV 1 beschränkt hatte. Dies ändert aber nichts daran, dass die Rekurskommission sich an den Streitgegenstand der Bewilligung von regelmässig wiederkehrender Sonntagsarbeit an maximal 20 Sonn- und Feiertagen hielt. Sie durfte den erstinstanzlichen Bewilligungsentscheid durchaus mit anderer rechtlicher Begründung schützen. Insofern unterscheidet sich der vorliegende Fall denn auch von demjenigen, der im von der Beschwerdeführerin angerufenen <ref-ruling> E. 1a S. 368 zu beurteilen war, hätte das dort strittige Vorbringen doch durchaus Auswirkungen auf die Rechtsfolge, nämlich die damals strittige und festzusetzende Steuer, gehabt, weshalb es sich um ein eigentliches neues Rechtsbegehren bzw. um eine Änderung des Streitgegenstandes handelte.
4. 4.1 Gemäss <ref-law> hat der Arbeitgeber Gesuche für im Gesetz vorgesehene Bewilligungen rechtzeitig einzureichen und zu begründen sowie die erforderlichen Unterlagen beizufügen. Nach Art. 41 ArGV 1 ist ein Gesuch schriftlich einzureichen und es hat die erforderlichen, in der Verordnungsbestimmung näher bezeichneten Angaben, insbesondere den Nachweis der Unentbehrlichkeit (lit. g), zu enthalten. Art. 42 ArGV 1 schreibt vor, dass in den behördlichen Arbeitszeitbewilligungen unter anderem die Rechtsgrundlage und die Begründung der Bewilligung anzuführen ist. Nach Meinung der Beschwerdeführerin dienen diese Vorschriften dazu, den gesetzeskonformen Gang des Bewilligungsverfahrens sicherzustellen. Im vorliegenden Fall seien weder die Beschwerdegegnerin noch die Bewilligungsbehörde den ihnen jeweils obliegenden Pflichten nachgekommen.
4.2 Im Arbeitsgesetz sind die Anforderungen an ein Gesuch lediglich allgemein definiert, und es enthält keine besonderen Bestimmungen zur Bewilligungsbegründung, weshalb insoweit grundsätzlich die allgemeinen aus <ref-law> und <ref-law> abgeleiteten Rechtsregeln gelten. Immerhin umschreibt das Verordnungsrecht die entsprechenden Pflichten näher. Es kann aber nicht Anforderungen stellen, die über die gesetzlichen Pflichten hinausgehen. Nach <ref-law> stellt die Behörde den Sachverhalt von Amtes wegen fest (vgl. Moser, a.a.O., Rz. 1.5; Rhinow/Koller/Kiss, a.a.O., Rz. 904 ff.). Sie wendet auch das Recht von Amtes wegen an, wobei insbesondere Rechtsmittelinstanzen nicht an die Rechtsauffassung der unteren Instanzen gebunden sind (vgl. Moser, a.a.O., Rz. 1.8; Rhinow/Koller/ Kiss, a.a.O., Rz. 915 ff.).
4.3 Obwohl es sich bei den Bewilligungen für Sonntagsarbeit um Ausnahmegenehmigungen handelt, hat das seco insgesamt eine Vielzahl von Gesuchen für Arbeitsbewilligungen zu behandeln. Die Anforderungen des Verordnungsrechts an Bewilligungsgesuche dienen daher nicht nur dazu, ein gesetzeskonformes Verfahren sicherzustellen, sondern sie bezwecken auch, den Aufwand der Bewilligungsbehörde möglichst klein zu halten. Da das Verordnungsrecht nicht strengere Vorschriften aufstellen kann als das Gesetz, darf das seco nicht einfach auf Gesuche nicht eintreten, die den gesetzlichen Bestimmungen entsprechen, aber nicht die detaillierteren Anforderungen der Verordnung erfüllen. Bei einer solchen Ausgangslage kann die Bewilligungsbehörde in Zusammenarbeit mit dem Gesuchsteller dessen Gesuch konkretisieren und ergänzende Abklärungen vornehmen, weshalb das entsprechende Vorgehen des seco im vorliegenden Fall Bundesrecht nicht verletzt. Auch die Begründung der Bewilligungsentscheide darf kurz gehalten werden, obwohl es in der Tat wünschbar erscheint, dass wenigstens die angewandte Rechtsgrundlage bzw. der von der Behörde als erfüllt erachtete Tatbestand daraus hervorgehen, wie die Beschwerdeführerin geltend macht.
In diesem Sinne lässt sich ebenfalls der Mangel eines allenfalls unvollständigen Gesuchs bzw. einer allenfalls ungenügenden Sachverhaltsabklärung oder Entscheidbegründung im Bewilligungs- oder Rechtsmittelverfahren beheben. Zwar ist einzuräumen, dass dadurch unter Umständen beschwerdeberechtigten Dritten wie im vorliegenden Zusammenhang den Arbeitnehmerverbänden die Wahrnehmung ihres Beschwerderechts erschwert wird. Dies ist aber bei den Anforderungen an die Beschwerdeerhebung und -begründung bzw. im Beschwerdeverfahren in Rechnung zu stellen und kann Auswirkungen auf die Verlegung der Verfahrenskosten und die Zusprechung einer Parteientschädigung zeitigen. Überhöhte Anforderungen an die Form der Gesuchseinreichung und Bewilligungsbegründung dienen der Sache hingegen nicht, sondern führen lediglich zu neuen Gesuchsverfahren und tragen das Risiko unnötiger Verzögerungen in sich, die für alle Beteiligten nachteilig sein können.
Im vorliegenden Fall wurden spätestens im Beschwerdeverfahren die sachliche und rechtliche Grundlage der strittigen Sonntagsarbeitsbewilligung sowie die Begründung für die Bewilligungserteilung in auch für die Beschwerdeführerin nachvollziehbarer Weise geklärt. Die Beschwerdeführerin wurde in diesem Zusammenhang nicht in ihren Verfahrensrechten beeinträchtigt, weshalb der angefochtene Entscheid insoweit nicht gegen Bundesrecht verstösst. Auf die Frage der Rechtmässigkeit der der Beschwerdeführerin von der Vorinstanz auferlegten Parteientschädigung zugunsten der Beschwerdegegnerin ist später zurückzukommen (dazu E. 7).
4.4 Unglücklich erscheint freilich, dass das seco unbestrittenermassen seinen Bewilligungsentscheid am 28. Mai 2002 im Bundesblatt publizierte, bevor es die letzten erfragten Unterlagen der Gesuchstellerin erhalten und am 4. Juni 2002 seine Verfügung getroffen hatte. Ein korrekter Ablauf erfordert, dass ein Bewilligungsentscheid erst veröffentlicht wird, nachdem er ergangen ist. Das bestreiten indessen auch die Vorinstanzen nicht, sondern sie erachten das Vorgehen des seco als ausnahmsweises - technisch bedingtes - Versehen. Die Publikation von Bewilligungsentscheiden im Arbeitsrecht dient der Transparenz der entsprechenden Praxis, deren allgemeinen politischen Kontrolle durch die Öffentlichkeit sowie der Wahrung der Beschwerderechte der Arbeitnehmerverbände. Die verfrühte Publikation eines Bewilligungsentscheids führt jedoch nicht automatisch zu dessen Ungültigkeit, wenn die veröffentlichte Version der tatsächlich gefällten Verfügung entspricht und wenn alle Verfahrensbeteiligten ihre Rechte wahren konnten, wenn dadurch insbesondere nicht die Ergreifung von Rechtsmitteln verunmöglicht oder unzulässigerweise erschwert wird. Im vorliegenden Verfahren entsprach der publizierte Entscheid der vom seco (nachträglich) gefällten Verfügung und die Beschwerdeführerin vermochte den erstinstanzlichen Entscheid frist- und formgerecht anzufechten. Auch insofern liegt demnach kein Verstoss gegen Bundesrecht vor.
5. 5.1 Nach Art. 41 lit. e ArGV 1 muss das Gesuch um eine Arbeitsbewilligung "die Bestätigung, dass das Einverständnis des Arbeitnehmers oder der Arbeitnehmerin eingeholt worden ist" enthalten. Nach Auffassung der Vorinstanz ist dieses Einverständnis nicht Voraussetzung der Bewilligungserteilung, sondern lediglich zum Arbeitseinsatz. Die Beschwerdeführerin erachtet dies als bundesrechtswidrig.
5.2 Art. 41 lit. e ArGV 1 setzt die Vorschrift von <ref-law> um, wonach der Arbeitgeber den Arbeitnehmer nicht ohne dessen Einverständnis zu Sonntagsarbeit heranziehen darf. Dabei ist erneut davon auszugehen, dass die Verordnungsbestimmung nicht strengere Voraussetzungen aufstellen darf als das Gesetz. Der Gesetzeswortlaut erscheint aber eindeutig: Er verlangt das Einverständnis der Arbeitnehmer nicht als Voraussetzung der Bewilligungserteilung, sondern als solche des Arbeitseinsatzes. Insoweit weicht der Verordnungstext von der gesetzlichen Regelung ab. Die Auslegung der fraglichen Bestimmungen durch die Vorinstanz, die im Übrigen gemäss dem angefochtenen Entscheid im vorliegenden Fall nicht zum ersten Mal Anwendung gefunden hat, ist daher grundsätzlich nicht zu beanstanden.
5.3 Die Beschwerdeführerin wendet dagegen allerdings ein, es laufe nicht auf dasselbe hinaus, ob der Arbeitgeber im Voraus, wenn er ein Gesuch um Sonntagsarbeit stelle, von den potentiell betroffenen Arbeitnehmern eine Zustimmungserklärung einhole oder ob er bei schon vorliegender Sonntagsarbeitsbewilligung einen konkreten Arbeitseinsatz verlange; im zweiten Fall könne sich ein Arbeitnehmer im Hinblick auf allfällige Repressalien zwar rechtlich, kaum aber tatsächlich weigern, Sonntagsarbeit zu leisten. Dieser im Kern zutreffende Einwand vermag aber den klaren Wortlaut des Gesetzes nicht umzustossen. Die Bewilligungsbehörde hat dem fraglichen Zusammenhang vielmehr auf andere Weise Rechnung zu tragen; so hat sie etwa entsprechenden Hinweisen nachzugehen, wenn Anhaltspunkte dafür bestehen, dass ein Arbeitgeber seine Arbeitnehmer unzulässigerweise zu Sonntagsarbeit verpflichtet, und die nötigen Massnahmen bis hin zu behördlichen Sanktionen oder den Widerruf der Bewilligung zu ergreifen (vgl. <ref-law>). Dass es im vorliegenden Fall konkrete Hinweise auf entsprechende gesetzeswidrige Verhaltensweisen der Beschwerdegegnerin gibt, macht aber auch die Beschwerdeführerin, die sich lediglich auf die abstrakte Möglichkeit des faktischen Zwangs zu Sonntagsarbeit beruft, nicht geltend.
Im Übrigen war den Arbeitnehmern der Beschwerdegegnerin aufgrund der Einzelarbeitsverträge und der Betriebsordnung der Beschwerdegegnerin bekannt, dass bei ihrer Arbeitgeberin Sonntagseinsätze vorkommen. Dem entspricht, dass bei der Beschwerdegegnerin bereits seit geraumer Zeit Sonntagsarbeit geleistet wird. Das ersetzt zwar das Erfordernis des Einverständnisses für solche Einsätze nicht. Die Frage der Sonntagsarbeit trifft die betroffenen Arbeitnehmer aber jedenfalls nicht unvorbereitet.
6. 6.1 In der Sache begründet die Vorinstanz die Bewilligung für Sonntagsarbeit bei der Beschwerdegegnerin mit der erheblichen Beeinträchtigung von deren Konkurrenzfähigkeit wegen längerer Arbeitszeiten oder anderer Arbeitsbedingungen im Ausland (Art. 28 Abs. 2 lit. c ArGV 1). Nach Ansicht der Beschwerdeführerin stellt die Vorinstanz insofern zu niedrige Anforderungen. Nebst der als bundesrechtswidrig beanstandeten Auslegung und Anwendung der einschlägigen Bestimmungen von Gesetz und Verordnung erachtet die Beschwerdeführerin die Sachverhaltsfeststellung der Vorinstanz als unvollständig.
6.2 Gemäss Art. 105 Abs. 2 OG ist das Bundesgericht im Verfahren der Verwaltungsgerichtsbeschwerde an die Feststellung des Sachverhalts gebunden, wenn wie hier eine richterliche Behörde als Vorinstanz entschieden und diese den Sachverhalt nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen erhoben hat.
6.3 Das Sonntagsarbeitsverbot beruht auf christlicher Tradition und leitet sich vor allem aus sozialen und kulturellen Zusammenhängen ab. Der für alle gleiche freie Tag verschafft dem in die Arbeit eingespannten Menschen körperliche und geistige Erholung und Musse. Kollektive Freizeit ermöglicht darüber hinaus Kommunikation und Kontakte in der Familie sowie im Freundes- und Bekanntenkreis in einem Masse, wie es individuelle Wochenfreizeiten nicht zu leisten vermögen (vgl. <ref-ruling> E. 3a S. 333; <ref-ruling> E. 4a S. 275, 284 E. 4a S. 288). Wer am Sonntag arbeitet, muss denn auch Nachteile in familiärer, kultureller und sozialer Hinsicht in Kauf nehmen (BBl 1994 II 168). Gemäss der gesetzlichen Regelung genügt blosse Zweckmässigkeit für ein Abweichen vom Sonntagsarbeitsverbot nicht. Erforderlich ist vielmehr Unentbehrlichkeit. Dabei ist Ansatzpunkt für die Beurteilung der wirtschaftlichen Unentbehrlichkeit nicht die wirtschaftliche Lage des einzelnen Betriebs, sondern das Arbeitsverfahren, was eine wettbewerbsneutrale Praxis bei der Erteilung von Ausnahmebewilligungen erlaubt (<ref-ruling> E. 5a S. 335; <ref-ruling> E. 4c S. 276 f., 284 E. 4c S. 289).
Die Ausnahme vom Sonntagsarbeitsverbot wegen erheblicher Beeinträchtigung der Konkurrenzfähigkeit gegenüber dem Ausland aufgrund längerer Arbeitszeiten oder anderer Arbeitsbedingungen hängt mit der weltwirtschaftlichen Verflechtung zusammen. Unterschiede in der Arbeitsgesetzgebung verbunden mit dem Abbau von Handelsschranken können zu einer Beeinträchtigung der Konkurrenzfähigkeit schweizerischer Betriebe führen, wenn in Konkurrenzländern weniger strenge Vorschriften gelten. Ausländische Standortvorteile infolge tieferen Lohnniveaus sollen allerdings nicht durch entsprechende Ausnahmen ausgeglichen werden. In Betracht fällt vielmehr einzig eine Beeinträchtigung der Wettbewerbsfähigkeit, die auf weniger strenge Arbeitsschutzvorschriften im Ausland zurückgeht. Solche Unterschiede können Sonntagsarbeit auch in der Schweiz wirtschaftlich unentbehrlich machen (vgl. <ref-ruling> E. 5b S. 335 f.; <ref-ruling> E. 5d S. 279 f., 284 E. 5d S. 293).
Im Hinblick auf den gesetzgeberischen Grundentscheid, Sonntagsarbeit möglichst einzuschränken, verlangt das Verordnungsrecht jedoch einen Vergleich mit Ländern "mit vergleichbarem sozialem Standard". Der Schutz des Arbeitnehmers hat in diesem Sinne nur zurückzutreten, wenn Länder mit sozial grundsätzlich gleichwertiger Regelung in bestimmten Branchen weniger strenge Vorschriften kennen, vorausgesetzt allerdings, dass mit diesen Ländern eine Konkurrenzsituation besteht und erhebliche Auswirkungen auf die Konkurrenzfähigkeit der schweizerischen Unternehmungen nachgewiesen sind (vgl. <ref-ruling> E. 5d S. 280, 284 E. 5d S. 293 f.).
6.4 Im Vergleich zur Rechtslage, welche für <ref-ruling> sowie <ref-ruling> und 284 galt, hat der Gesetzeswortlaut geändert. Während damals Sonntagsarbeit (bzw. der teilweise zu beurteilende ununterbrochene Betrieb) unter den gesetzlichen Voraussetzungen bewilligt werden "konnte" (vgl. Art. 19 Abs. 1 bzw. <ref-law> in der alten Fassung vom 13. März 1964 [AS 1966 65 f.] sowie <ref-ruling> E. 2a S. 272), steht der Bewilligungsbehörde heute kein entsprechendes Ermessen mehr zu. Obwohl der Gesetzgeber dem Sonntagsarbeitsverbot noch immer eine grosse Bedeutung beimisst (vgl. BBl 1994 II 168 sowie BBl 1998 S. 1394 ff.; vgl. dazu auch das Urteil des Bundesgerichts 2A.542/2001 vom 1. Oktober 2002, E. 4.1), gewichtet er heute die Ausnahmetatbestände in dem Sinne stärker, dass nunmehr ein Anspruch auf Bewilligung besteht, wenn die Voraussetzungen der Genehmigung von Sonntagsarbeit erfüllt sind. Das Gesetz setzt aber die Unentbehrlichkeit der Sonntagsarbeit noch immer voraus, und die Kriterien der bisherigen bundesgerichtlichen Rechtsprechung zum alten Recht sind weiterhin anwendbar (vgl. dazu <ref-ruling> E. 5a S. 109 f. sowie das Urteil des Bundesgerichts 2A.166/2003 vom 7. August 2003, E. 2).
6.5 Für die Beschwerdegegnerin findet sich in der Schweiz keine massgebliche Konkurrenz. Ihre Konkurrenzfähigkeit bemisst sich daher ausschliesslich im internationalen Vergleich. Im vorliegenden Zusammenhang verzichtete die Vorinstanz wegen fraglicher Vergleichbarkeit des sozialen Standards auf einen Vergleich mit Unternehmen in Russland und Polen und beschränkte sich auf einen solchen mit zwei zum gleichen Konzern wie die Beschwerdegegnerin gehörenden Konkurrenzbetrieben in Deutschland und Frankreich. Dazu stellte die Rekurskommission fest, das Unternehmen in Deutschland habe ab Mai 2003 über eine Bewilligung für ununterbrochenen, dauernden Sonn- und Feiertagsbetrieb verfügt, welche bis zum 31. Dezember 2003 befristet gewesen sei, danach aber mit gewissen Auflagen um zwei Jahre verlängert werden sollte. Die Auslastung der Tiefdruckanlage habe an Sonntagen durchschnittlich über 50 % betragen, wobei drei Schichten zu acht Stunden für insgesamt 27 Arbeitnehmer geleistet worden seien. Im Vergleichsbetrieb in Frankreich habe vom 1. Januar bis zum 14. Juli 2003 insgesamt an 26 Sonntagen und zwar in der Regel mit mindestens 15 Arbeitnehmern in zwei Schichten zu zwölf Stunden gearbeitet werden können, was zu einer durchschnittlichen Auslastung der dortigen zwei Tiefdruckanlagen von ebenfalls 50 % geführt habe.
Das Bundesgericht ist an diese tatsächlichen Feststellungen der Rekurskommission gebunden (vgl. E. 6.2). Zu prüfen ist jedoch, ob der von der Vorinstanz vorgenommene Vergleich die rechtlichen Vorgaben der Arbeitsgesetzgebung einhält und ob er für die Erteilung einer Ausnahmebewilligung genügt.
6.6 Unbestritten ist, dass es sich bei Frankreich und Deutschland um Länder mit vergleichbarem sozialem Standard handelt, die für einen Vergleich nach Art. 28 Abs. 2 lit. c ArGV 1 grundsätzlich in Frage kommen. Entgegen der Auffassung der Beschwerdeführerin ist nicht ersichtlich, weshalb ein Vergleich mit zwei Konkurrenzbetrieben aus zwei unterschiedlichen Staaten als Grundlage für eine Ausnahme vom Sonntagsarbeitsverbot nicht genügen sollte. Wenn eine Konkurrenzsituation besteht und die Konkurrenzfähigkeit wegen der unterschiedlichen geltenden Arbeitsregelung beeinträchtigt ist, wovon das Bundesgericht mit der Vorinstanz in Anwendung von Art. 105 Abs. 2 OG auszugehen hat, dann besteht eine zureichende Grundlage für einen massgeblichen Vergleich. Immerhin wäre es an sich vorzuziehen, könnte ein Vergleich mit einem Konkurrenzunternehmen eines anderen Konzerns gezogen werden; das Bundesrecht verbietet einen Vergleich mit einem ausländischen Betrieb desselben Konzerns aber nicht (vgl. schon <ref-ruling> E. 5d S. 294). Das hat jedenfalls solange zu gelten, als ein Missbrauch bzw. eine Gesetzesumgehung nicht konkret nachgewiesen oder wenigstens glaubhaft gemacht wird. Der entsprechende Einwand der Beschwerdeführerin, ein internationaler Konzern könnte sonst die Arbeitsbedingungen in verschiedenen Ländern unter Hinweise auf die (an sich rein interne) Konkurrenzsituation praktisch nach Belieben steuern, ist lediglich genereller Natur, und die Beschwerdeführerin belegt einen solchen Zusammenhang im vorliegenden Fall nicht. Im Übrigen trifft der Einwand in dieser allgemeinen Form auch nicht zu: Wie die Beschwerdeführerin selbst ausführt, kennen die Arbeitsgesetze in vergleichbaren Staaten regelmässig dieselben oder ähnliche Voraussetzungen für die Bewilligung von Sonntagsarbeit wie die Schweiz. Es braucht also gleich wie in der Schweiz eine besondere Ausgangslage, um Sonntagsarbeit zu rechtfertigen, womit Gesetzesumgehungen bzw. die Ausschaltung nationaler Verbote von Sonntagsarbeit auch für einen internationalen Konzern nicht ohne weiteres möglich erscheinen. Richtig ist immerhin, dass ein gewisser Dominoeffekt eintreten kann, wenn in einem Land eine Ausnahmebewilligung erhältlich ist. Dies trifft indessen wegen der erforderlichen Vergleichbarkeit des sozialen Standards auch nur dann zu, wenn die rechtlichen Hürden mit denjenigen in der Schweiz grundsätzlich vergleichbar sind.
Weiter ist nicht zu beanstanden, dass der Vergleichsbetrieb in Deutschland lediglich über eine befristete Genehmigung für Sonntagsarbeit verfügte. Vielmehr kommt es entscheidend auf die tatsächliche Konkurrenzsituation an, wobei jegliche Bewilligung von Sonntagsarbeit, selbst wenn diese befristet ist, einen Wettbewerbsvorteil zu verschaffen vermag. Im Übrigen werden solche Bewilligungen auch in der Schweiz nur befristet erteilt (vgl. Art. 42 Abs. 2 ArGV 1).
Entgegen der Auffassung der Beschwerdeführerin durfte die Vorinstanz sodann ihren Vergleich im Wesentlichen auf die Arbeitszeiten abstützen. Bereits der Verordnungstext spricht von einer Beeinträchtigung der Konkurrenzfähigkeit wegen längerer Arbeitszeiten "oder" anderer Arbeitsbedingungen. Es ist also grundsätzlich nicht ausgeschlossen, einzig auf die Arbeitszeiten abzustellen. Immerhin erschiene dies im Hinblick auf das grundsätzliche gesetzliche Verbot der Sonntagsarbeit unzulässig, wenn klare Hinweise darauf bestünden, dass abgesehen von der Arbeitszeit die Arbeitsbedingungen insgesamt in der Schweiz deutlich schlechter wären. Derartige klare Anhaltspunkte gibt es im vorliegenden Fall jedoch nicht. Die Beschwerdeführerin weist zwar auf gewisse Unterschiede hin. Solche bestehen aber zwangsläufig zwischen verschiedenen Staaten, und auch die Beschwerdeführerin liefert keine Anhaltspunkte für massgebliche schlechtere Arbeitsbedingungen in der Schweiz. So mag zwar insbesondere das schweizerische Arbeitsgesetz keinen Lohnzuschlag für Sonntagsarbeit vorsehen; solche Lohnzuschläge sind aber auch in der Schweiz üblich, und die Beschwerdegegnerin ist aufgrund ihrer Arbeitsverträge zur Zahlung einer erheblichen Lohnzulage für Sonntagsarbeit verpflichtet. Insoweit einzig auf die Rechtslage und nicht auf die tatsächlichen Gegebenheiten abzustellen, würde einem realistischen Vergleich nicht gerecht. Im Übrigen enthält <ref-law> ergänzende Vorschriften, die bei Sonntagsarbeit im Interesse der Arbeitnehmer zu wahren sind, wie etwa solche über den Ausgleich von geleisteter Sonntagsarbeit.
6.7 Die Vorinstanz hat im angefochtenen Entscheid mit Blick auf Art. 28 Abs. 2 lit. c ArGV 1 vorwiegend die Konkurrenzfähigkeit der Beschwerdegegnerin mit ausländischen Betrieben geprüft. Obwohl sie im Ergebnis die Erheblichkeit der Beeinträchtigung der Konkurrenzfähigkeit nicht ausdrücklich erwähnte, so geht doch klarerweise aus ihrer Begründung hervor, dass sie nicht von einer bloss unmassgeblichen Beschränkung ausging. Analoges gilt für die Voraussetzung der grossen Wahrscheinlichkeit der Sicherung der Beschäftigung. Ohne das Vorliegen dieser Voraussetzung ausdrücklich zu nennen, wies die Rekurskommission doch auf die angespannte internationale Konkurrenzsituation hin. Sie ging offensichtlich davon aus, dass die Gefahr einer Verlagerung des Auftragsvolumens von der Beschwerdegegnerin weg zu ihren Konkurrenzbetrieben in Frankreich und Deutschland drohe, und sie erwähnte ausdrücklich das Schicksal eines weiteren Konkurrenzunternehmens in Irland, das kurz vor der Schliessung stand. Auch diese Feststellungen sind für das Bundesgericht verbindlich.
Die Beschwerdeführerin ist zwar der Ansicht, die Vorinstanz hätte auch einen umfassenden Vergleich der Maschinenlaufzeiten zwischen der Beschwerdegegnerin und ihrer ausländischen Konkurrenz vornehmen müssen. Dies erscheint bereits deshalb fraglich, weil die entsprechenden Daten in der Regel kaum erhältlich sein dürften. Die Konkurrenzfähigkeit bemisst sich aber ohnehin nicht einzig an den Laufzeiten der technischen Installationen, sondern es gibt wesentliche andere Kriterien wie insbesondere eine gewisse Flexibilität bei der Befriedigung der Nachfrage, wie sie gerade von der Beschwerdegegnerin geltend gemacht wird. Die Rekurskommission durfte daher eine erhebliche Beeinträchtigung der Konkurrenzfähigkeit bejahen, ohne die Maschinenlaufzeiten im Detail zu vergleichen.
6.8 Insgesamt ist der vorliegende Fall entgegen der Auffassung der Beschwerdeführerin nur bedingt mit <ref-ruling> vergleichbar. Da es sich bei der damaligen Vorinstanz nicht um eine gerichtliche Behörde handelte, konnte das Bundesgericht deren Sachverhaltsfeststellungen, im Unterschied zum vorliegenden Fall, frei überprüfen. Überdies hatte die damalige Vorinstanz überhaupt keine Abklärungen zu den tatsächlichen Verhältnissen in Konkurrenzländern vorgenommen. Vorliegend vermied die Rekurskommission denselben Mangel, indem sie angesichts ihrer Zweifel, ob der von der Bewilligungsbehörde angewandte Ausnahmetatbestand der unvermeidlich hohen Investitionskosten gemäss Art. 28 Abs. 2 lit. b ArGV 1 erfüllt sei, im Hinblick auf Art. 28 Abs. 2 lit. c ArGV 1 die erforderlichen Abklärungen zur Konkurrenzsituation mit dem Ausland nachholte. Die Vorinstanz klärte dabei den einschlägigen Sachverhalt in genügendem Masse ab, und sie hielt sich an die rechtlichen Voraussetzungen für die Genehmigung von Sonntagsarbeit. Mehr zu verlangen, würde die Anforderungen an die Bewilligung von Sonntagsarbeit überspannen und wäre mit dem Risiko der Belastung des Bewilligungsverfahrens in einer Art und Weise verbunden, dass der Rahmen einer effizienten Verwaltung gesprengt würde. Solches verlangt auch der Arbeitsschutz nicht, selbst wenn das Prinzip des Sonntagsarbeitsverbots mit der bisherigen bundesgerichtlichen Rechtsprechung weiterhin als bedeutsam erachtet werden muss und auch künftig zu verlangen ist, dass die gesetzlichen Voraussetzungen für Ausnahmen strikt eingehalten werden. Sind diese Voraussetzungen aber erfüllt, ist die Bewilligung gemäss den bundesrechtlichen Bestimmungen (bzw. gemäss <ref-law> für dauernde oder regelmässig wiederkehrende Sonntagsarbeit) zu erteilen. Auch insofern unterscheidet sich der vorliegende Fall, wie dargelegt (vgl. E. 6.4), von <ref-ruling>.
6.9 Die Erteilung der strittigen Bewilligung für Sonntagsarbeit erweist sich damit nicht als bundesrechtswidrig.
7. 7.1 Zu prüfen bleibt, ob der Entscheid der Vorinstanz, der Beschwerdeführerin eine ungekürzte Parteientschädigung von Fr. 5'000.-- (inkl. Mehrwertsteuer) zugunsten der Beschwerdegegnerin aufzuerlegen, vor Bundesrecht standhält.
7.2 Nach <ref-law> kann die Beschwerdeinstanz der ganz oder teilweise obsiegenden Partei eine Entschädigung für ihr erwachsene notwendige und verhältnismässig hohe Kosten zusprechen. Parteikosten gelten dann als notwendig, wenn sie zur sachgerechten und wirksamen Rechtsverfolgung oder Rechtsverteidigung unerlässlich erscheinen (Moser, a.a.O., Rz. 4.16). Unnötige Kosten begründen demgegenüber keinen Anspruch auf Parteientschädigung (Art. 8 Abs. 5 der Verordnung vom 10. September 1969 über Kosten und Entschädigungen im Verwaltungsverfahren; SR 172.041.0; Moser, a.a.O., Rz. 4.18; vgl. auch Art. 159 Abs. 5 i.V.m. Art. 156 Abs. 6 OG).
7.3 Die Beschwerdeführerin ist vor der Vorinstanz vollständig unterlegen, womit sie grundsätzlich entschädigungspflichtig wurde. Indessen änderte vor der Rekurskommission zwar nicht der Streitgegenstand, wohl aber die rechtliche Argumentation. Diese inhaltliche Verlagerung des Rechtsstreites hat die Beschwerdegegnerin massgeblich mitverursacht. Zunächst hatte sie vor der erstinstanzlichen Bewilligungsbehörde ihr Bewilligungsgesuch nur allgemein und rudimentär begründet und jedenfalls keine genügenden Belege dafür eingereicht, dass die Voraussetzungen gemäss Art. 28 Abs. 2 lit. c ArGV 1 erfüllt waren. Auch vor der Rekurskommission als Beschwerdeinstanz berief sie sich zunächst auf den Ausnahmetatbestand von Art. 28 Abs. 2 lit. b ArGV 1; erst in der Duplik begründete sie ihren Bewilligungsanspruch zum ersten Mal in verbindlicher Weise mit dem Ausnahmetatbestand von Art. 28 Abs. 2 lit. c ArGV 1, was eingehende Abklärungen durch die Vorinstanz sowie einen zusätzlichen Austausch von Rechtsschriften auslöste. Die Beschwerdegegnerin ist damit ihrer gesetzlichen Pflicht nach <ref-law> in Verbindung mit Art. 41 ArGV 1 nur unvollständig nachgekommen. Zwar durften die Vorinstanzen diesen Mangel in Zusammenarbeit mit der Beschwerdegegnerin beheben (dazu E. 4), doch ist dies beim Entscheid über die Zusprechung einer Parteientschädigung in Rechnung zu stellen. Durch eine Verfahrensführung, die von Beginn an die alternative - und schliesslich ausschlaggebende - Begründung umfassend und unter Beachtung der gesetzlichen Anforderungen an ein Bewilligungsgesuch mitberücksichtigt hätte, hätte der Aufwand massgeblich verringert werden können. Die Beschwerdegegnerin hat sich damit einen erheblichen Anteil der entstandenen Kosten selber zuzuschreiben, weshalb diese insoweit nicht als notwendig gelten können.
Unter diesen Umständen verstösst es gegen Bundesrecht, wenn die Vorinstanz entschied, die Beschwerdeführerin habe der Beschwerdegegnerin deren Parteikosten ungekürzt zu entschädigen. Die Verwaltungsgerichtsbeschwerde ist daher in diesem Punkt gutzuheissen, und der angefochtene Entscheid muss insoweit aufgehoben werden. Aus prozessökonomischen Gründen ist die Parteientschädigung für das vorinstanzliche Verfahren direkt neu festzusetzen (vgl. Art. 114 Abs. 2 OG). Dabei rechtfertigt sich angesichts des Verfahrensablaufs eine 50-prozentige Kürzung, was bedeutet, dass die Beschwerdeführerin die Beschwerdegegnerin für das Verfahren vor der Rekurskommission mit Fr. 2'500.-- zu entschädigen hat.
8. Demnach ist die Verwaltungsgerichtsbeschwerde teilweise gutzuheissen, und Ziff. 3 des Dispositivs des angefochtenen Entscheids muss aufgehoben werden. Die Parteientschädigung für das vorinstanzliche Verfahren ist neu auf Fr. 2'500.-- (inkl. Mehrwertsteuer) festzusetzen. Im Übrigen muss die Verwaltungsgerichtsbeschwerde abgewiesen werden.
Bei diesem Verfahrensausgang sind die Kosten des bundesgerichtlichen Verfahrens beiden Parteien aufzuerlegen, wobei die hauptsächlich unterliegende Beschwerdeführerin die Gerichtsgebühr zu 4/5 und die Beschwerdegegnerin zu 1/5 zu tragen hat. Überdies hat die Beschwerdeführerin der Beschwerdegegnerin für das Verfahren vor dem Bundesgericht eine reduzierte Parteientschädigung auszurichten.

Demnach erkennt das Bundesgericht:
1. 1.1 Die Verwaltungsgerichtsbeschwerde wird teilweise gutgeheissen, und die Ziffer 3 des Dispositivs des Entscheids der Rekurskommission des Eidgenössischen Volkswirtschaftsdepartements vom 2. Juni 2004 wird aufgehoben.
1.2 Die Beschwerdeführerin hat der Beschwerdegegnerin für das Verfahren vor der Rekurskommission des Eidgenössischen Volkswirtschaftsdepartements eine reduzierte Parteientschädigung von Fr. 2'500.-- (inkl. Mehrwertsteuer) auszurichten.
1.3 Im Übrigen wird die Verwaltungsgerichtsbeschwerde abgewiesen.
2. Die Gerichtsgebühr von Fr. 5'000.-- wird der Beschwerdeführerin zu 4/5 (mithin im Betrag von Fr. 4'000.--) und der Beschwerdegegnerin zu 1/5 (mithin im Betrag von 1'000.--) auferlegt.
3. Die Beschwerdeführerin hat der Beschwerdegegnerin für das bundesgerichtliche Verfahren eine reduzierte Parteientschädigung von Fr. 3'000.-- auszurichten.
4. Dieses Urteil wird den Parteien, dem Staatssekretariat für Wirtschaft (seco) und der Rekurskommission des Eidgenössischen Volkswirtschaftsdepartements schriftlich mitgeteilt.
Lausanne, 16. Februar 2005
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: