Fatti: A. A._, di formazione aiuto-medico, a partire dal 1985 ha conseguito vari diplomi presso istituti privati nei settori della Leibtherapie, della cromopuntura secondo il metodo di Peter Mandel, della medicina esogetica e della terapia sonora. Dal 1992 svolge un'attività professionale indipendente nel Cantone di Zugo quale terapista complementare nel campo della cromopuntura e della cromoterapia. B. Il 28 ottobre 2006, allegando i propri diplomi ed un'attestazione del medico cantonale di Zugo, A._ ha chiesto all'Ufficio di sanità del Cantone Ticino di poter esercitare la propria attività anche in detto cantone. Con decisione del 16 maggio 2007 l'autorità adita ha respinto l'istanza, adducendo in sostanza che in Ticino, diversamente che a Zugo, l'autorizzazione quale terapista complementare presuppone il superamento di un esame cantonale. Di conseguenza l'istante non poteva rientrare in questa categoria, ma soltanto in quella dei guaritori. Su ricorso, il 23 aprile 2008 il Consiglio di Stato ha confermato tale pronuncia. Contro la decisione governativa l'interessata è allora insorta dinanzi al Tribunale cantonale amministrativo, presso la quale, con atto separato, si è aggravata pure la Commissione della concorrenza. Con sentenza del 10 ottobre 2008 la Corte cantonale ha accolto i ricorsi, accertando che le decisioni inferiori limitavano in modo inammissibile l'accesso al mercato e rinviando gli atti all'Ufficio di sanità affinché autorizzasse incondizionatamente l'istante all'esercizio della professione di terapista complementare nei settori della cromopuntura, della cromoterapia e della terapia sonora. C. Il 19 novembre 2008 il Cantone Ticino ha presentato un ricorso in materia di diritto pubblico dinanzi al Tribunale federale. In via principale, chiede che la sentenza del Tribunale amministrativo sia annullata e che A._ sia ammessa ad esercitare la propria attività unicamente come guaritrice. In via subordinata, domanda che l'interessata sia autorizzata a praticare quale terapista complementare secondo la legislazione ticinese, ma sia astretta a superare entro due anni l'esame previsto da tale ordinamento. In via ancor più subordinata, postula che all'interessata sia semplicemente concesso il nulla osta ad esercitare anche in Ticino trattamenti non scientificamente riconosciuti ai sensi delle normative del Canton Zugo. D. A._ chiede che, nella misura in cui risulti ammissibile, il ricorso venga respinto. La Commissione della concorrenza propone anch'essa la conferma della sentenza impugnata. L'Ufficio di sanità dichiara invece di condividere l'impugnativa, mentre il Tribunale cantonale amministrativo si riconferma nella motivazione e nelle conclusioni del proprio giudizio. E. Il 29 gennaio 2009 l'Ufficio di sanità ha risolto di ammettere provvisoriamente A._ al libero esercizio nel Cantone quale terapista complementare nei settori della cromopuntura, della cromoterapia e della terapia sonora. L'autorizzazione è stata concessa fino alla sentenza del Tribunale federale.