Sachverhalt:
A. Das Arbeitsinspektorat des Kantons Appenzell A.Rh. auferlegte der X._ GmbH & Co. KG, gestützt auf Art. 9 Abs. 2 lit. a des Bundesgesetzes vom 8. Oktober 1999 über die minimalen Arbeits- und Lohnbedingungen für in die Schweiz entsandte Arbeitnehmerinnen und Arbeitnehmer und flankierende Massnahmen (Entsendegesetz, EntsG; SR 823.20) eine Verwaltungsbusse von Fr. 1500.-- wegen Verletzung von Meldevorschriften. Das kantonale Departement Volks- und Landwirtschaft bestätigte diesen Entscheid auf Rekurs hin am 17. Januar 2007. Das Verwaltungsgericht von Appenzell Ausserrhoden, an welches sich die gebüsste Firma daraufhin gewandt hatte, hob den Entscheid des Departementes mit Urteil vom 29. August 2007 (versandt am 14. Mai 2008) auf, und zwar vorab mit der Begründung, dass die Befugnis zur Ausfällung der streitigen Sanktion nicht beim Arbeitsinspektorat, sondern gemäss der allgemeinen Vorschrift von Art. 1 der kantonalen Strafprozessordnung bei den Strafverfolgungsorganen liege; die durch regierungsrätliche Verordnung erfolgte Kompetenzzuweisung an das Arbeitsinspektorat entbehre der erforderlichen formellgesetzlichen Grundlage. Die Beschwerde wäre zudem, wie das Verwaltungsgericht in einer Eventualbegründung darlegte, selbst bei Bejahung der Zuständigkeit des Arbeitsinspektorates aus materiellen Gründen gutzuheissen.
B. Das Departement Volks- und Landwirtschaft führt hiegegen namens des Kantons Appenzell A.Rh. Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Begehren, das Urteil des Verwaltungsgerichts vom 29. August 2007 aufzuheben und die ausgefällte Busse zu bestätigen; eventuell sei wenigstens festzustellen, dass das kantonale Arbeitsinspektorat als "zuständige kantonale Behörde" im Sinne von <ref-law> befugt sei, Sanktionen nach <ref-law> auszusprechen.
C. Das Verwaltungsgericht des Kantons Appenzell A.Rh. beantragt Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Beschwerdegegnerin hat auf eine Stellungnahme verzichtet.

Erwägungen:
1. Angefochten ist ein letztinstanzlicher kantonaler Endentscheid in einer Angelegenheit, deren tatsächliches Schwergewicht - es geht aus der Sicht des Beschwerdeführers vor allem um die Vereinbarkeit der auf Verordnungsstufe verankerten Bussenkompetenz des kantonalen Arbeitsinspektorates mit der Kompetenzordnung der Kantonsverfassung - kantonales öffentliches Recht betrifft, wobei der Streitgegenstand an sich unter keinen der Ausschlussgründe gemäss <ref-law> fällt. Insofern könnte - entsprechend der dem angefochtenen Urteil beigefügten Rechtsmittelbelehrung - das Rechtsmittel der Beschwerde in öffentlich-rechtlichen Angelegenheiten offen stehen. Formeller Verfahrensgegenstand bildet jedoch die Ausfällung einer Verwaltungsbusse gemäss <ref-law>, womit als zu ergreifendes Rechtsmittel auch die Beschwerde in Strafsachen in Betracht fällt (vgl. dazu Urteil 6B_205/2007 vom 27. Oktober 2007, E. 1). Welches dieser beiden Rechtsmittel bei der hier gegebenen Konstellation gegeben ist, kann aufgrund der folgenden Erwägungen offen bleiben.
2. Das rekurrierende kantonale Departement bezeichnet seine Eingabe als Beschwerde in öffentlich-rechtlichen Angelegenheiten. Es kann sich für die Ergreifung dieses Rechtsmittels unbestrittenermassen auf keine besondere Ermächtigungsnorm im Sinne von <ref-law> stützen. Das Departement handelt nicht als Behörde, sondern tritt explizit als Vertreter des Kantons auf, der durch das ergangene Verwaltungsgerichtsurteil in schutzwürdigen eigenen Interessen betroffen und damit gestützt auf <ref-law> zur Beschwerde legitimiert sei. Die Beeinträchtigung schutzwürdiger Interessen wird darin erblickt, dass der Kanton Appenzell A.Rh. die ihm aufgrund des Entsendegesetzes zukommende Kontrolle faktisch nicht mehr ausüben könne, bis der kantonale Gesetzgeber die geforderte formellgesetzliche Grundlage für die Bussenkompetenz des administrativen Kontrollorgans geschaffen habe. Darüber wäre mit einem volkswirtschaftlichen Schaden (Benachteiligung des einheimischen Gewerbes sowie Wettbewerbsverzerrungen) zu rechnen, weil ausländische Arbeitgeber im Kanton sanktionsfrei Lohn- und Sozialdumping betreiben könnten. Schliesslich bestehe die Gefahr, dass bereits gebüsste Arbeitgeber bei Feststellung der Unzuständigkeit des Arbeitsinspektorates die bezahlten Bussgelder zurückfordern könnten.
3. Wenn ein Kanton gestützt auf <ref-law> als Rechtsmittelkläger handeln will, obliegt seine prozessuale Vertretung in der Regel dem Regierungsrat als oberster Exekutivbehörde. Will eine nachgeordnete Behörde namens des Kantons Beschwerde führen, hat sie ihre Vertretungsbefugnis explizit darzutun, sei es durch einen entsprechenden speziellen Ermächtigungsbeschluss der Kantonsregierung oder durch Angabe der sie zur Prozessführung namens des Kantons berechtigenden kantonalen Vorschriften (zur Publ. bestimmtes Urteil 2C_15/2008 vom 13. Oktober 2008, E. 1.2.3). Diese Rechtsprechung war dem beschwerdeführenden kantonalen Departement bei Einreichung seiner Eingabe noch nicht bekannt. Auf eine Fristansetzung zur nachträglichen Begründung der beanspruchten Beschwerdelegitimation bzw. zur Einreichung eines Ermächtigungsbeschlusses wird daher verzichtet. Für künftige Verfahren bleibt dieser Nachweis vorbehalten.
4. 4.1 Nach der bundesgerichtlichen Rechtsprechung kann das allgemeine Beschwerderecht von <ref-law> auch vom Gemeinwesen in Anspruch genommen werden, wenn es durch den angefochtenen Entscheid gleich oder ähnlich wie ein Privater betroffen ist. Darüber hinaus kann die Legitimation des Gemeinwesens ebenfalls gegeben sein, wenn es in schutzwürdigen eigenen hoheitlichen Interessen berührt ist. Das kann bei vermögensrechtlichen Interessen zutreffen, aber auch bei Eingriffen in spezifische eigene öffentliche Sachanliegen. Das blosse allgemeine Interesse an der richtigen Rechtsanwendung verschafft aber noch keine Rechtsmittelbefugnis nach <ref-law>. Ebensowenig genügt auch nicht jedes beliebige, mit der Erfüllung einer öffentlichen Aufgabe direkt oder indirekt verbundene finanzielle Interesse des Gemeinwesens für eine Inanspruchnahme des allgemeinen Beschwerderechts (<ref-ruling> E. 2.2.1 S. 46 f. mit Hinweisen).
4.2 Durch einen Beschwerdeentscheid, welcher die kantonale Behörde in einem Einzelfall zur Erteilung einer streitigen Bewilligung verpflichtet, wird der Kanton als Gemeinwesen regelmässig noch nicht in einem relevanten Ausmass in schutzwürdigen hoheitlichen Interessen berührt, welches ihm ein Beschwerderecht nach <ref-law> zu verschaffen vermöchte (so betreffend eine ausländerrechtliche Bewilligung: <ref-ruling> E. 2.2.2 S. 47 f.; betreffend eine Bewilligung zur selbständigen Berufsausübung: zur Publ. vorgesehenes Urteil 2C_15/2008 vom 13. Oktober 2008, E. 1.2.2). Nicht anders verhält es sich, wenn, wie vorliegend, eine von einer kantonalen Behörde ausgefällte Verwaltungsbusse durch eine Rechtsmittelinstanz aufgehoben oder korrigiert wird. Für eine Inanspruchnahme des allgemeinen Beschwerderechts durch das mit der Rechtsanwendung betraute Gemeinwesen besteht in solchen Fällen kein Raum; der Weiterzug bleibt jenen Behörden oder Organisationen vorbehalten, die sich hiefür auf eine besondere gesetzliche Ermächtigung stützen können (<ref-law>; vgl. auch <ref-law>).
5. 5.1 Soweit die richtige Anwendung der Meldevorschriften des Entsendegesetzes im Verwaltungsverfahren in Frage steht, kommt die Befugnis zur Beschwerdeführung gestützt auf <ref-law> dem für diesen Aufgabenbereich zuständigen Departement des Bundes (Eidgenössisches Volkswirtschaftsdepartement, EVD) sowie den allenfalls hierzu besonders ermächtigten, diesem unterstellten Dienststellen zu. Der Kanton kann die beschwerdeberechtigte Bundesbehörde zur Ergreifung des Rechtsmittels einladen, aber nicht - als Gemeinwesen - selber Beschwerde in öffentlich-rechtlichen Angelegenheiten führen. Entsprechendes gilt, wenn die Ausfällung einer Strafsanktion wegen Verletzung der genannten Verwaltungsvorschriften in Frage steht; zur Erhebung der Beschwerde in Strafsachen sind nur die in <ref-law> genannten Parteien und Behörden berechtigt.
5.2 Es fragt sich, ob die dem Kanton Appenzell A.Rh. aus dem angefochtenen Verwaltungsgerichtsurteil für den Vollzug des Entsendegesetzes erwachsenden Erschwernisse eine Beschwerdelegitimation nach <ref-law> zu begründen vermögen. Das seitens des Kantons angeführte Risiko, durch das Arbeitsinspektorat bereits ausgefällte Verwaltungsbussen zurückerstatten zu müssen, dürfte kaum bestehen; die allfällige Unzuständigkeit des Arbeitsinspektorates wäre nicht derart offensichtlich, dass frühere, rechtskräftig gewordene Entscheide als geradezu nichtig erscheinen könnten. Mehr Gewicht kommt dem Einwand zu, dass der Kanton bis zum Erlass einer formellgesetzlichen Regelung die ihm gemäss Entsendegesetz zukommenden Aufgaben nicht mehr oder nicht mehr effizient erfüllen könne. Zur prozessualen Geltendmachung dieses Interesses wären nach dem Gesagten wohl wiederum in erster Linie die nach <ref-law> beschwerdeberechtigten Bundesorgane berufen. Im vorliegenden Fall stützt sich das angefochtene Urteil allerdings auf die innerkantonale verfassungsrechtliche Kompetenzordnung, mit deren Auslegung und Wahrung sich die Bundesbehörden nicht zu befassen haben. Durch das seitens des Verwaltungsgerichts geltend gemachte verfassungsrechtliche Hindernis wird der Kanton Appenzell A.Rh. bis zum Erlass einer dahingehenden formellgesetzlichen Regelung daran gehindert, die in <ref-law> vorgesehene Sanktionsbefugnis zur Durchsetzung der minimalen Arbeits- und Lohnbedingungen für in die Schweiz entsandte Arbeitnehmer durch das Arbeitsinspektorat ausüben zu lassen. Dem Kanton bleibt jedoch nach den Erwägungen des Verwaltungsgerichts die Möglichkeit, auf dem Verordnungsweg kurzfristig eine Übergangslösung vorzusehen, wonach die betreffenden Sanktionen - auf Anzeige des Arbeitsinspektorates hin - von einer Strafbehörde verhängt werden. Das angefochtene Urteil beruht möglicherweise auf einer Verkennung der Tragweite der organisationsrechtlichen Vorgaben des Entsendegesetzes, doch ist zweifelhaft, ob der Kanton dadurch in einem Masse in schutzwürdigen eigenen hoheitlichen Interessen beeinträchtigt wird, welches die Anerkennung eines Beschwerderechts nach <ref-law> zu rechtfertigen vermöchte.
6. Die aufgeworfene Frage kann jedoch offen bleiben. Das Verwaltungsgericht begründet die Aufhebung der angefochtenen Verwaltungsbusse nicht allein mit der fehlenden Zuständigkeit des Arbeitsinspektorates, sondern rechtfertigt seinen Entscheid in einer Eventualbegründung zusätzlich damit, dass seitens der sanktionierten Firma gar keine Verletzung der Meldevorschriften gemäss Entsendegesetz vorliege. Beruht eine Entscheidung auf zwei oder mehreren Begründungen, muss jede derselben angefochten werden (vgl. <ref-ruling> E. 7 S. 228; <ref-ruling> E. 3 S. 17). Die vorliegende Beschwerdeschrift befasst sich im Wesentlichen einzig mit der umstrittenen Bussenkompetenz des kantonalen Arbeitsinspektorates. Zwar wird auch die Bestätigung der ausgefällten Busse von Fr. 1500.-- beantragt und unter Hinweis auf eine beigelegte 15-seitige Stellungnahme des Arbeitsinspektorates vom 12. Juni 2008 geltend gemacht, die erwähnte Eventualbegründung beruhe auf unrichtigen Sachverhaltsannahmen und verneine zu Unrecht eine Verletzung der Meldepflichten gemäss Entsendegesetz. Die Begründung einer Beschwerde muss in der Rechtsmitteleingabe selber enthalten sein; blosse Verweise auf andere Rechtsschriften oder sonstige Dokumente genügen nicht (<ref-ruling> E. 3.2 S. 400). Ob die beigelegte Stellungnahme des kantonalen Arbeitsinspektorates hier als Beschwerdebegründung entgegenzunehmen wäre, kann dahingestellt bleiben. Jedenfalls ist der Kanton, soweit es allein darum geht, ob die Meldevorschriften in einem einzelnen Fall richtig angewendet worden sind, nach dem Gesagten (oben E. 4.2 und 5.1) zur Beschwerde nicht legitimiert. Die prozessuale Sachlage ist damit gleich wie im Fall, dass von zwei selbständigen Begründungen eine gar nicht angefochten wird. Sofern die Beschwerde in öffentlich-rechtlichen Angelegenheiten vorliegend überhaupt zulässig sein sollte (oben E. 1), stünde einer materiellen Beurteilung jedenfalls die fehlende Legitimation des Kantons zur Anfechtung der erwähnten Eventualbegründung entgegen. Entsprechendes würde gelten, wenn das vorliegende Rechtsmittel als Beschwerde in Strafsachen zu behandeln wäre (E. 1). Auf die Beschwerde ist daher nicht einzutreten.
7. Da der Kanton Appenzell A.Rh. keine vermögensrechtlichen Interessen verfolgt, ist er von der Bezahlung der Gerichtskosten befreit (<ref-law>). Die Beschwerdegegnerin hat auf eine Stellungnahme verzichtet, womit die Zusprechung einer Parteientschädigung entfällt (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Es werden keine Gerichtskosten erhoben.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien, dem Arbeitsinspektorat des Kantons Appenzell A.Rh. und dem Verwaltungsgericht von Appenzell Ausserrhoden, 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 10. November 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Moser