Die Volkswirtschafts- und die Polizeidirektion des Kantons Appenzell A.Rh. erliessen am 19. Juni 1995 gemeinsame Richtlinien "betreffend die Bewilligungspraxis für ausländische Künstler, Musiker, Artisten, Tänzer, Tänzerinnen und Discjockeys" (im folgenden: Richtlinien). Danach wird auf Tänzer und Tänzerinnen in Nachtclubs oder ähnlichen Lokalen, deren Darbietungen der erotischen Unterhaltung dienen, Art. 8 der Verordnung vom 6. Oktober 1986 über die Begrenzung der Zahl der Ausländer (Begrenzungsverordnung, BVO; SR 823.21) angewendet; Bewilligungen werden deshalb grundsätzlich nur noch an EU/EFTA-Angehörige erteilt (Ziffer 2.4).

Auf die von Rudolf Kreis, Inhaber des Cabaret Rebluus in Tobel, sowie fünf weiteren Betreibern von Nachtclubs im Kanton Appenzell A.Rh. hiergegen eingereichte staatsrechtliche Beschwerde tritt das Bundesgericht nicht ein.

Aus den Erwägungen:

2.- a) Die von den Beschwerdeführern beanstandeten Richtlinien wenden sich an die zuständigen Fremdenpolizeibehörden und sollen eine einheitliche Verwaltungspraxis sicherstellen; es handelt sich somit um eine Verwaltungsverordnung. Solche verwaltungsinternen, nicht von den zuständigen Rechtsetzungsorganen ausgehenden Weisungen vermögen an sich keine Rechte und Pflichten der Bürger zu begründen (vgl. Art. 84 Abs. 1 OG; vgl. BGE 119 Ia 214 E. 2a S. 217). Sie sind mit staatsrechtlicher Beschwerde nur anfechtbar, sofern sie indirekt geschützte Rechte des Bürgers berühren und damit Aussenwirkungen entfalten, ohne dass gegen den betroffenen Einzelnen eine förmliche Verfügung ergeht, die er wegen Verletzung seiner verfassungsmässigen Rechte wirksam und für ihn zumutbar anfechten könnte (BGE 105 Ia 349 E. 2a S. 351 ff.; vgl. auch BGE 114 Ia 452 E. 1a S. 455; Urteil vom 20. Juli 1994 i.S. Hauseigentümer-Verband Zürich u. Mitb., E. 1a, in ZBl 96/1995 S. 44 ff., WALTER KÄLIN, Das Verfahren der staatsrechtlichen Beschwerde, 2. Aufl., Bern 1994, S. 142 ff., KURT STAMPFLI, Rechtliche Probleme allgemeiner Dienstanweisungen, Diss. Freiburg 1982, S. 275 ff.).

b) Eine weitere Schranke ergibt sich aus Art. 88 OG. Danach ist zur staatsrechtlichen Beschwerde nur legitimiert, wer durch den angefochtenen Hoheitsakt in rechtlich geschützten eigenen Interessen betroffen wird; zur Verfolgung bloss tatsächlicher Interessen steht dieses Rechtsmittel nicht offen. Die eigenen rechtlichen Interessen, auf die sich der Beschwerdeführer berufen muss, können entweder durch kantonales oder eidgenössisches Gesetzesrecht oder aber unmittelbar durch ein angerufenes spezielles Grundrecht geschützt sein, sofern sie auf dem Gebiet liegen, welches dieses beschlägt (BGE 121 I 267 E. 2 S. 269). Das Erfordernis eines Eingriffs in rechtlich geschützte Interessen gilt auch für die Legitimation zur Anfechtung von rechtsetzenden Erlassen. Zwar genügt hier eine virtuelle Betroffenheit, doch muss es immer um einen drohenden Eingriff in rechtlich geschützte Interessen gehen (BGE 118 Ia 427 E. 2a S. 430 f., 119 Ia 197 E. 1c S. 200 f., 321 E. 2b S. 324). Dies gilt auch bei Verwaltungsverordnungen (BGE 98 Ia 508 E. 1 S. 511, bereits zitiertes Urteil vom 20. Juli 1994, E. 1a): Eine staatsrechtliche Beschwerde ist gegen solche Weisungen nur zulässig, sofern die beanstandete Regelung gesetzlich oder verfassungsrechtlich geschützte Interessen des Beschwerdeführers berührt.

3.- a) Die Beschwerdeführer gehen davon aus, dass gegen die beanstandeten Richtlinien kein wirksamer Rechtsschutz bestehe, weil sie die ihnen bis Ende 1995 zustehenden Kontingente für das Engagement von Tänzerinnen bereits zugeteilt erhalten hätten. Sie könnten daher zurzeit keine Verfügungen über weitere Bewilligungen mehr erwirken; es sei ihnen nicht zuzumuten, mehr als ein halbes Jahr zu warten, um dann die auf den neuen Richtlinien beruhenden Verfügungen auf dem Rechtsweg anzufechten.

Ob auf ihre Beschwerde deshalb einzutreten ist, erscheint zweifelhaft, kann aber dahingestellt bleiben, da die Beschwerdeführer weder durch einzelne Verfügungen noch durch die beanstandeten Richtlinien in gesetzlich oder verfassungsrechtlich geschützten Interessen betroffen werden (Art. 88 OG).

b) aa) Die zuständigen Behörden entscheiden über Aufenthaltsbewilligungen im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland nach freiem Ermessen (Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer, ANAG; SR 142.20). Die von den Beschwerdeführern angerufene Verordnung vom 6. Oktober 1986 über die Begrenzung der Zahl der Ausländer legt ihrerseits lediglich die formellen und materiellen Schranken fest, welche die Kantone bei der Erteilung von Aufenthaltsbewilligungen zu beachten haben. Sie verpflichtet sie aber nicht, solche zu erteilen, und begründet damit keine Rechtsansprüche (vgl. Art. 100 lit. b Ziff. 3 OG: BGE 115 Ib 1 E. 1b S. 3). Dies gilt auch für Art. 8 BVO, der die prioritären Rekrutierungsgebiete bzw. geographische Schranken für die Zulassung von ausländischen Arbeitskräften festlegt. Die Kantone sind nicht verpflichtet, den durch diese Bestimmung eröffneten Spielraum bei ihrer Bewilligungspraxis voll auszunützen. Da sich die Anträge auf Aufenthaltsbewilligungen für Tänzerinnen aus Ländern ausserhalb der EU und der EFTA regelmässig nicht auf eine spezielle (gesetzliche oder völkerrechtliche) Grundlage stützen können, besteht auch insofern kein Rechtsanspruch (weshalb gegenüber abschlägigen kantonalen Entscheiden die Verwaltungsgerichtsbeschwerde an das Bundesgericht ausgeschlossen ist; vgl. Art. 100 lit. b Ziff. 3 OG).

bb) Das in Art. 4 BV enthaltene allgemeine Willkürverbot verschafft für sich allein noch keine geschützte Rechtsstellung im Sinne von Art. 88 OG; die Legitimation zur Willkürbeschwerde ist nur gegeben, wenn das Gesetzesrecht, dessen willkürliche Anwendung gerügt wird, dem Beschwerdeführer einen Rechtsanspruch einräumt oder den Schutz seiner Interessen bezweckt (BGE 121 I 267 E. 2 S. 268 f., mit Hinweisen). Dass auf die Erteilung von Aufenthaltsbewilligungen der hier in Frage stehenden Art kein gesetzlicher Anspruch besteht, wurde bereits dargelegt. Damit entfällt die Legitimation zur staatsrechtlichen Beschwerde, soweit es um die Geltendmachung des allgemeinen Willkürverbots geht. Die Rüge, die beanstandete Praxisänderung beruhe auf keinen haltbaren sachlichen Gründen und sei deshalb willkürlich, ist somit nicht zu hören.

cc) Entgegen der Ansicht der Beschwerdeführer ergibt sich das erforderliche rechtlich geschützte Interesse auch nicht aus dem mitangerufenen Grundrecht der Handels- und Gewerbefreiheit (Art. 31 BV). Wohl garantiert dieses dem Arbeitgeber grundsätzlich die freie Wahl seiner Mitarbeiter. Diese Freiheit bezieht sich indessen nicht auf den Einsatz von Arbeitskräften, die im Arbeitsmarkt noch nicht zugelassen sind. So wenig wie der Ausländer selber aus Art. 4 oder Art. 31 BV einen Anspruch auf Aufenthaltsbewilligung ableiten kann, so wenig verschafft die Handels- und Gewerbefreiheit dem interessierten schweizerischen Arbeitgeber einen verfassungsrechtlich geschützten Anspruch auf Erteilung einer Aufenthaltsbewilligung (BGE 114 Ia 307 E. 3b S. 312). Das allgemeine Gleichbehandlungsgebot nach Art. 4 BV und der in Art. 31 BV enthaltene - weitergehende - Grundsatz der Gleichbehandlung der Gewerbegenossen schützen nicht davor, dass ausserhalb des Kantons Appenzell A.Rh. gelegene Konkurrenzbetriebe möglicherweise in den Genuss einer günstigeren fremdenpolizeilichen Bewilligungspraxis kommen; dies ist eine hinzunehmende Folge des föderalistischen Aufbaus des schweizerischen Staatswesens (vgl. BGE 121 I 49 E. 4c S. 53, 104 Ia 156 E. 2b S. 158).

dd) Wieweit ein legitimationsbegründender Rechtsanspruch auf Erteilung einer Aufenthaltsbewilligung allenfalls aus dem Gebot des Vertrauensschutzes (zu dessen Umschreibung vgl. BGE 118 Ia 245 E. 4b S. 254, mit Hinweis) abgeleitet werden könnte, braucht hier nicht weiter untersucht zu werden. Die Beschwerdeführer vermögen sich auf keine konkreten behördlichen Zusicherungen zu berufen, die der beschlossenen Praxisänderung entgegenstehen würden; sie konnten sich aufgrund der bisherigen Bewilligungspraxis allein nicht darauf verlassen, dass diese in Zukunft nicht verschärft würde, zumal die Ergreifung von Abwehrmassnahmen gegen Missstände auf diesem Gebiet schon seit einiger Zeit zur Diskussion stand. Von einem Verstoss gegen die Schranken des Vertrauensschutzes kann somit nicht die Rede sein.

ee) Schliesslich verschafft auch der angerufene Grundsatz der derogatorischen Kraft des Bundesrechts (Art. 2 ÜbBest. BV) keine Beschwerdelegitimation nach Art. 88 OG. Die Vorschriften der Begrenzungsverordnung begründen keine Rechtsansprüche, gegen welche die Anwendung der neuen Richtlinien verstossen könnte. Zudem liegt die behauptete Normenkollision offensichtlich gar nicht vor, da sich die beanstandete Ziffer 2.4 der Richtlinien innerhalb des durch die Begrenzungsverordnung gegebenen Rahmens hält. Art. 8 BVO kann durch die beanstandete restriktive kantonale Bewilligungspraxis deshalb gar nicht verletzt sein.

c) Wenn vorliegend gegenüber den "Aussenwirkungen" der beanstandeten Verwaltungsverordnung, d.h. gegenüber den im betreffenden Regelungsbereich ergehenden Verfügungen, wie dargelegt, auf Bundesebene kein Rechtsschutz besteht, weil es den Betroffenen an einem Rechtsanspruch im Sinne von Art. 100 lit. b Ziff. 3 OG bzw. an einem rechtlich geschützten Interesse im Sinne von Art. 88 OG fehlt, ist auch gegen die entsprechende Verwaltungsverordnung als solche die staatsrechtliche Beschwerde unzulässig. Zwar ist nicht ausgeschlossen, dass eine staatsrechtliche Beschwerde gegen  Richtlinien, die bestimmte Bewerberkategorien diskriminieren, ausnahmsweise auch dort möglich wäre, wo gegen die jeweilige Einzelverfügung (in der Sache) grundsätzlich keine Legitimation nach Art. 88 OG besteht, z.B. im Bereich von Submissionen oder bei der Zulassung zum öffentlichen Dienst. Vorliegend geht es jedoch nicht um die Diskriminierung einzelner Gruppen von Gesuchstellern, sondern um eine generelle Anordnung, die den gesamten Interessentenkreis (bzw. alle Nachtclub-Betreiber im Kanton) in gleicher Weise trifft, ohne in gesetzlich oder verfassungsrechtlich geschützte Rechte einzugreifen. Auf die staatsrechtliche Beschwerde ist daher nicht einzutreten.