Faits: A. Le 28 septembre 2004, le Service cantonal valaisan de protection des travailleurs et des relations du travail (ci-après: le Service cantonal) a accordé à la Société des Arts et Métiers et Commerçants de Sion et environs (ci-après: la Société des Arts et Métiers) l'autorisation d'occuper du personnel dans les magasins sis sur la commune de Sion le dimanche 19 décembre 2004, cela en relation avec un marché de Noël. Le 25 octobre 2004, les syndicats FTMH à Berne, SIB à Zurich et UNIA à Bâle, ont recouru contre cette décision auprès du Conseil d'Etat. Par prononcé du 15 décembre 2004, ce dernier a rejeté le recours. Saisi d'un recours formé par le syndicat UNIA, regroupant dorénavant la FTMH et le SIB, le Tribunal cantonal du canton du Valais, Cour de droit public (ci-après: le Tribunal cantonal) a, par arrêt du 25 mai 2005, annulé la décision du Conseil d'Etat du 15 décembre 2004. En substance, il a d'abord estimé devoir faire abstraction de l'absence d'intérêt actuel. Ensuite, se fondant sur la jurisprudence du Tribunal fédéral, il a nié l'existence d'un besoin urgent permettant de déroger au principe de l'interdiction du travail dominical selon l'art. 19 al. 3 de la loi fédérale du 13 mars 1964 sur le travail dans l'industrie, l'artisanat et le commerce (Loi sur le travail, LTr; RS 822.11). Il a notamment considéré que, si un marché de Noël existait bien à Sion depuis de nombreuses années, il n'y avait, en revanche, pas de tradition d'ouverture dominicale des commerces durant cette période, non plus que de forte concurrence étrangère à contrecarrer pour des raisons économiques. B. Agissant par la voie du recours de droit administratif, la Société des Arts et Métiers conclut à l'annulation de l'arrêt précité du 25 mai 2005. Le Tribunal cantonal renonce à se déterminer et le Conseil d'Etat se réfère à l'arrêt attaqué, tandis que la ville de Sion conclut à l'admission du recours et le syndicat UNIA à son rejet. Le Département fédéral de l'économie estime que l'autorisation délivrée en l'espèce par le Service cantonal remplit les conditions fixées par la loi et la pratique du Secrétariat d'Etat à l'économie (seco).