Familiennachzug, hat sich ergeben:
A.- X._, geboren 1976, Schweizer Bürger, heiratete am 6. August 1999 die jugoslawische Staatsangehörige J.S._, geboren 1964. Am 11. August 1999 ersuchte X._ um eine Aufenthaltsbewilligung für seine Ehefrau und deren aus erster Ehe stammenden Kinder A._, geboren 1981, B._, geboren 1985, C._, geboren 1987, D._, geboren 1992, sowie E._, geboren 1993.
B.- Mit Verfügung vom 9. Dezember 1999 wies das Departement des Innern des Kantons Solothurn das Gesuch von X._ ab. Zur Begründung führte es an, während ein Nachzug der ältesten Tochter schon deshalb nicht in Frage komme, weil diese bei Gesuchseinreichung bereits 18-jährig gewesen sei, müsse das Gesuch hinsichtlich der minderjährigen Kinder mangels genügender finanzieller Mittel für den Unterhalt der Familie abgewiesen werden. Der Ehefrau könne keine Aufenthaltsbewilligung erteilt werden, weil die Ehe nicht eingegangen worden sei, um eine Familiengemeinschaft zu begründen, sondern um die Wegweisung zu verhindern.
C.- Gegen die Verfügung des Departements des Innern vom 9. Dezember 1999 erhob X._ beim Verwaltungsgericht des Kantons Solothurn Beschwerde, mit der er um Erteilung einer Aufenthaltsbewilligung für seine Ehefrau und deren minderjährige Kinder ersuchte; in Bezug auf die volljährige Tochter A._ verzichtete er auf die Anfechtung der fraglichen Verfügung. Im Weiteren ersuchte er um die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung für das Verfahren vor Verwaltungsgericht.
Mit Urteil vom 11. Juli 2000 wies das Verwaltungsgericht des Kantons Solothurn die Beschwerde ab, wobei es der Argumentation des Departements des Innern im Wesentlichen folgte. Da das Verwaltungsgericht in einem Punkt eine - nach seiner Auffassung im Beschwerdeverfahren geheilte und somit für den Ausgang unerhebliche - Verletzung des rechtlichen Gehörs feststellte, sprach es dem Anwalt von X._ eine reduzierte Parteientschädigung von Fr. 600.-- zu. Im Übrigen überband es den auf den Beschwerdeführer entfallenden Anteil der Verfahrenskosten von Fr. 1'000.-- dem Staat und setzte das Honorar des unentgeltlichen Rechtsbeistands auf Fr. 1'200.-- fest.
D.- Mit Eingabe vom 14. September 2000 hat X._ beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht.
Er beantragt, das Urteil des Verwaltungsgerichts vom 11. Juli 2000 sei aufzuheben und seiner Ehefrau und deren Kindern B._, C._, D._ und E._ seien Aufenthaltsbewilligungen zu erteilen; eventuell sei die Sache an das Verwaltungsgericht zurückzuweisen; subeventuell sei das Verwaltungsgericht zu verpflichten, das volle Armenrechtshonorar und eine Parteientschädigung auf der Basis eines Stundenansatzes von Fr. 200.-- zuzusprechen.
Sodann ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung für das Verfahren vor Bundesgericht.
Das Amt für öffentliche Sicherheit des Kantons Solothurn, Abteilung Ausländerfragen, sowie das Bundesamt für Ausländerfragen schliessen auf Abweisung der Beschwerde.
Das Verwaltungsgericht des Kantons Solothurn beantragt, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne.
E.- Dem vom Beschwerdeführer mit Schreiben vom 10. Oktober 2000 gestellten Gesuch um aufschiebende Wirkung wurde mit Verfügung des Abteilungspräsidenten vom 8. November 2000 entsprochen.

Das Bundesgericht zieht in Erwägung:
1.- a) aa) Art. 100 Abs. 1 lit. b Ziff. 3 OG schliesst die Verwaltungsgerichtsbeschwerde auf dem Ge- biete der Fremdenpolizei aus gegen die Erteilung oder Verweigerung von Bewilligungen, auf die das Bundesrecht keinen Anspruch einräumt. Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) entscheiden die zuständigen Behörden, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Es besteht damit grundsätzlich kein Anspruch auf Erteilung einer Aufenthaltsbewilligung, es sei denn, der Ausländer oder seine in der Schweiz lebenden Angehörigen könnten sich auf eine Sondernorm des Bundesrechts oder eines Staatsvertrages berufen (<ref-ruling> E. 1a S. 337 f., 377 E. 2 S. 381, 425 E. 1 S. 427; <ref-ruling> E. 2a S. 291, 361 E. 1a S. 364; <ref-ruling> E. 1b S. 147, je mit Hinweisen).
bb) Nach Art. 7 Abs. 1 ANAG (in der Fassung vom 23. März 1990) hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung; der Anspruch erlischt, wenn ein Ausweisungsgrund vorliegt. Für die Eintretensfrage ist einzig darauf abzustellen, ob formell eine eheliche Beziehung besteht; anders als bei Art. 8 der Konvention vom 4. November 1950 zum Schutze der Menschenrechte und Grundfreiheiten (Europäische Menschenrechtskonvention, EMRK; SR 0.101) ist nicht erforderlich, dass die Ehe intakt ist und tatsächlich gelebt wird (<ref-ruling> E. 1b S. 266, 425 E. 2a S. 427; <ref-ruling> E. 1b S. 292; <ref-ruling> E. 2b S. 18; <ref-ruling> E. 3d S. 151). Es kommt daher in diesem Zusammenhang auch nicht darauf an, ob die Ehegatten überhaupt je zusammengelebt haben (<ref-ruling> E. 2c S. 419; bestätigt in BGE <ref-ruling> E. 1b S. 292).
cc) Im vorliegenden Fall lebt der Beschwerdeführer zwar getrennt von seiner ausländischen Ehefrau, die Ehe besteht aber jedenfalls formell. Die Ehefrau des Beschwerdeführers besitzt somit grundsätzlich einen Rechtsanspruch auf die Erteilung einer Aufenthaltsbewilligung gemäss Art. 7 Abs. 1 Satz 1 ANAG, weshalb das Rechtsmittel der Verwaltungsgerichtsbeschwerde zulässig ist. Die Frage, ob die Bewilligung verweigert werden durfte, weil einer der in Art. 7 ANAG vorgesehenen Ausnahmetatbestände oder ein Verstoss gegen das Rechtsmissbrauchsverbot gegeben ist, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1b S. 266 mit Hinweisen sowie BGE <ref-ruling> E. 2b S. 18; <ref-ruling> E. 2d S. 419; <ref-ruling> E. 3d S. 151).
b) aa) Mit der Verwaltungsgerichtsbeschwerde kann vorliegend die Verletzung von Bundesrecht, einschliesslich Überschreitung oder Missbrauch des Ermessens, sowie die unrichtige oder unvollständige Feststellung des rechtserheblichen Sachverhalts (Art. 104 lit. a und b OG), nicht jedoch die Unangemessenheit des angefochtenen Entscheids (vgl. Art. 104 lit. c OG) gerügt werden. Zufolge des engen Sachzusammenhangs mit den zu beurteilenden bundesrechtlichen Fragen ist auch die dem angefochtenen Entscheid zugrunde liegende Handhabung kantonalen Verfahrensrechts unter dem Gesichtswinkel der Bundesrechtskonformität, d.h. insbesondere auf allfällige Verstösse gegen Bundesverfassungsrecht (vgl. <ref-ruling> E. 3a S. 509), im verwaltungsgerichtlichen Beschwerdeverfahren zu prüfen (<ref-ruling> E. 1b/ aa S. 277 f.; Walter Kälin, Das Verfahren der staatsrechtlichen Beschwerde, 2. Auflage, Bern 1994, S. 300 f.).
bb) Hat - wie hier - eine richterliche Behörde als Vorinstanz entschieden, ist das Bundesgericht an deren Sachverhaltsfeststellung gebunden, sofern diese nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen erfolgt ist (Art. 105 Abs. 2 OG). Damit wird die Möglichkeit, vor Bundesgericht neue Tatsachen vorzubringen und neue Beweismittel einzureichen, weitgehend eingeschränkt. Das Bundesgericht lässt diesfalls nur solche neuen Tatsachen und Beweismittel zu, welche die Vorinstanz von Amtes wegen hätte berücksichtigen müssen und deren Nichtbeachtung eine Verletzung wesentlicher Verfahrensvorschriften darstellt (<ref-ruling> E. 1c S. 99 f., 110 E. 2c S. 114; <ref-ruling> E. 1b S. 169; <ref-ruling> E. 2a S. 79 f.; Fritz Gygi, Bundesverwaltungsrechtspflege, 2. Auflage, Bern 1983, S. 286/287). Nachträgliche Veränderungen des Sachverhalts (sog. "echte" Noven) können in der Regel nicht mehr berücksichtigt werden, denn einer Behörde ist nicht vorzuwerfen, sie habe den Sachverhalt im Sinne von Art. 105 Abs. 2 OG fehlerhaft festgestellt, wenn sich dieser nach ihrem Entscheid verändert hat (<ref-ruling> E. 3a S. 221; Alfred Kölz/Isabelle Häner, Verwaltungsverfahren und Verwaltungsrechtspflege des Bundes, 2. Auflage, Zürich 1998, Rz. 943). Insofern können der in der nachträglichen Eingabe vom 13. Dezember 2000 erwähnte Arbeitsunfall des Beschwerdeführers und eine allfällige, dadurch entstandene Pflegebedürftigkeit im vorliegenden Verfahren genauso wenig berücksichtigt werden wie der in der Beschwerde erstmals vorgebrachte Umstand, dass die Ehefrau und die Kinder während den Schulferien beim Beschwerdeführer weilen.
cc) Wer Verwaltungsgerichtsbeschwerde erhebt, hat eine Beschwerdeschrift einzureichen, welche konkrete Begehren (Anträge) und deren Begründung enthalten muss (Art. 108 Abs. 2 OG). Nach der bundesgerichtlichen Rechtsprechung sind an Begehren und Begründung einer Verwaltungsgerichtsbeschwerde keine allzu hohen Anforderungen zu stellen. Erforderlich ist eine sachbezogene Begründung; es muss aus der Beschwerdeschrift ersichtlich sein, in welchen Punkten und weshalb der angefochtene Entscheid beanstandet wird (<ref-ruling> E. 2 S. 135 f.). Ein lediglich pauschaler Verweis auf frühere Rechtsschriften im gleichen Verfahren genügt der Begründungspflicht nicht (<ref-ruling> E. 1 S. 288; unveröffentlichte E. 3a von <ref-ruling>). Insofern erweist sich vorliegend der Verweis zur ergänzenden Begründung auf die Eingaben an das Verwaltungsgericht (S. 3 der Beschwerde) als unzulässig.
2.- Der Beschwerdeführer rügt in mehrfacher Hinsicht eine Verletzung seines Anspruches auf rechtliches Gehör durch die kantonalen Behörden.
Der in <ref-law> garantierte (vormals aus Art. 4 aBV abgeleitete) Anspruch auf rechtliches Gehör gibt dem Betroffenen das Recht, sich vor Erlass eines in seine Rechtsstellung eingreifenden Entscheids zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung von wesentlichen Beweisen mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen (<ref-ruling> E. 2a/aa S. 16; <ref-ruling> E. 3a S. 51, 241 E. 2 S. 242).
a) Der Beschwerdeführer bringt vor, er und seine Ehefrau seien vor dem Erlass der Verfügung des Departements des Innern nicht mit dem Vorwurf konfrontiert worden, es könnte sich bei ihrer Ehe um eine Scheinehe handeln. Die Vorinstanz verneinte eine Gehörsverletzung unter Hinweis darauf, dass dem Beschwerdeführer die Umstände seiner Heirat bekannt gewesen seien und lediglich die von Anfang an im Zentrum des Verfahrens stehende Bestimmung (Art. 7 ANAG) angewendet worden sei. Dem hält der Beschwerdeführer entgegen, es gehe nicht an, dass ein schweizerisch-ausländisches Ehepaar schon mit der Einreichung des Gesuchs, wofür ein entsprechendes Formular bestehe, vorsorglich auch zur Frage einer allfälligen Scheinehe Stellung nehmen müsse.
Bei der Frage, ob festgestellte Tatsachen darauf schliessen lassen, dass eine Ehe zwecks Umgehung fremdenpolizeilicher Vorschriften eingegangen worden ist und mithin eine Scheinehe vorliegt, handelt es sich nicht um eine Tat-, sondern um eine Rechtsfrage (vgl. <ref-ruling> E. 2a S. 6 f.; bestätigt in den unveröffentlichten Urteilen vom 28. April 2000 i.S. Bergamin, E. 2b/bb, vom 31. Januar 2000 i.S.
Sertdemir, E. 2b, und vom 17. Dezember 1999 i.S. Ratkovic, E. 2b). Nach der Rechtsprechung hat eine Partei lediglich dann Anspruch, sich zur rechtlichen Würdigung von ihr bekannten Tatsachen zu äussern, wenn die Behörde ihren Entscheid auf eine völlig neue rechtliche Basis zu stützen gedenkt, namentlich wenn sie den Entscheid mit einer Rechtsnorm oder einem Rechtsgrund zu begründen beabsichtigt, welche im bisherigen Verfahren weder erwähnt noch von einer der beteiligten Parteien geltend gemacht worden sind und mit deren Heranziehen sie auch nicht rechnen musste (vgl.
BGE 126 I 19 E. 2c/aa S. 22; <ref-ruling> E. 1a S. 185, je mit Hinweisen; Michele Albertini, Der verfassungsmässige Anspruch auf rechtliches Gehör im Verwaltungsverfahren des modernen Staates, Diss. Bern 2000, S. 270 f.). Dies ist vorliegend indessen nicht der Fall. Der Beschwerdeführer musste aufgrund der objektiven Umstände damit rechnen, dass das gestellte Familiennachzugsgesuch nicht ohne weiteres bewilligt werden würde und sich die Frage einer Ausländerrechtsehe stellen könnte. Was die tatsächlichen Verhältnisse anbelangt, so hätte es am Beschwerdeführer gelegen, die zu erwartenden naheliegenden Zweifel bereits im Gesuch zu entkräften, zumal ihn als Partei, welche das Verfahren durch eigenes Begehren eingeleitet hatte, eine Mitwirkungspflicht getroffen hat (vgl. <ref-ruling> E. 4c/cc S. 394). An diese Pflicht dürfen zwar hier keine überspannten Voraussetzungen geknüpft werden, geht es doch um die Erhebung von Tatsachen im Hinblick auf das mögliche Vorliegen einer Scheinehe, wofür die Fremdenpolizeibehörden beweispflichtig sind. Auch in einem solchen Verfahren kann es unter Umständen angezeigt oder sogar erforderlich sein, dem Betroffenen eine zusätzliche Gelegenheit zur Äusserung einzuräumen, namentlich wenn sich die zu ermittelnden Sachumstände dem für die Einreichung des Gesuchs vorgesehenen Formular nur teilweise entnehmen lassen und zusätzliche Abklärungen durch die Behörden notwendig sind (vgl. Albertini, a.a.O., S. 324, sowie generell zum Verhältnis von Mitwirkungsrecht und Mitwirkungspflicht S. 261 ff.). Eine allfällige diesbezügliche Gehörsverletzung, welche in der unterbliebenen Konfrontation des Beschwerdeführers mit den vom Departement geltend gemachten Indizien für das Vorliegen einer Scheinehe vor Erlass der Verfügung vom 9. Dezember 1999 erblickt werden könnte, wäre aber jedenfalls im Verfahren vor Verwaltungsgericht geheilt worden, weshalb die Beschwerde in diesem Punkt so oder so nicht durchzudringen vermag.
b) Der Beschwerdeführer macht geltend, das Departement des Innern habe Akten des kantonalen Zivilstandsamtes beigezogen, ohne ihn darüber informiert und um Stellungnahme angefragt zu haben, was von der Vorinstanz zu Unrecht als unbedenklich erklärt worden sei. Namentlich habe das Departement auf ein anlässlich einer Befragung des Beschwerdeführers durch das Zivilstandsamt aufgenommenes Protokoll abgestellt, über dessen Bedeutung im Hinblick auf dieses Verfahren er sich im damaligen Zeitpunkt nicht im Klaren gewesen sei. Dieses Protokoll habe sich nicht bei den Akten befunden, als dem Beschwerdeführer Akteneinsicht gewährt worden sei.
Eine Behörde, welche neue Unterlagen beizieht, auf die sie sich in ihrer Verfügung zu stützen gedenkt, ist grundsätzlich verpflichtet, die Beteiligten über den Beizug zu informieren (<ref-ruling> E. 2b S. 137 mit Hinweisen).
Der Beizug der Akten des kantonalen Zivilstandsamtes, welches den Beschwerdeführer zu den Umständen der Heirat einlässlich befragt hatte, lag an sich auf der Hand: Der Beschwerdeführer wusste um die Existenz des Befragungsprotokolles, welches ihm gemäss Stellungnahme des Amtes für öffentliche Sicherheit vom 12. Oktober 2000 in Kopie zugestellt worden sein soll, und er hätte auch die Bedeutung desselben für das vorliegende Verfahren erkennen müssen, zumal in der Einladung zum damaligen Gespräch auf "verschiedene Fragen" "im Zusammenhang mit der geplanten Eheschliessung" hingewiesen worden war und schliesslich anlässlich der Befragung auch mehrmals fremdenpolizeiliche Aspekte der Heirat zur Sprache gekommen waren. Insoweit musste der Beizug der Akten des Zivilstandsamtes nicht speziell avisiert werden (vgl. <ref-ruling> E. 2c S. 100); es genügte, dem Beschwerdeführer die fraglichen Akten zur Einsicht zur Verfügung zu halten (vgl. <ref-ruling> E. 2a S. 202 mit Hinweisen).
Allerdings war das betreffende Befragungsprotokoll - gemäss unbestritten gebliebener Darstellung des Beschwerdeführers - nicht bei den Akten des Amtes für öffentliche Sicherheit, welche dem Anwalt des Beschwerdeführers am 10. Januar 2000 zur Einsicht unterbreitet wurden. Doch war von dieser Befragung in der Vernehmlassung des genannten Amtes vom 3. April 2000 an die Vorinstanz (S. 3-5) die Rede.
Der Anwalt des Beschwerdeführers hätte somit Einsicht in das betreffende Protokoll sowie einen allfälligen weiteren Schriftenwechsel verlangen können. Wenn er dies unterlassen hat, kann er sich nicht nachträglich in diesem Punkt über eine Verletzung des rechtlichen Gehörs beklagen.
c) Der Beschwerdeführer rügt, das Departement habe - ohne Mitteilung an den Beschwerdeführer - auch Akten der Fremdenpolizei der Kantone Zürich und Aargau (letztere zusammen mit Unterlagen aus den Asylverfahren der Ehefrau des Beschwerdeführers) sowie verschiedene Schreiben der Gemeinde Sarmenstorf beigezogen. Das Verwaltungsgericht hat hierin eine Verletzung des rechtlichen Gehörs erblickt (S. 9 des angefochtenen Entscheids) und diesem Umstand bei der Kostenverteilung Rechnung getragen (S. 19 f.); den Mangel betrachtete es allerdings als im Rechtsmittelverfahren geheilt, was der Beschwerdeführer als unzutreffend erachtet.
Der Anspruch auf rechtliches Gehör ist formeller Natur; seine Verletzung führt ungeachtet der Erfolgsaussichten der Beschwerde in der Sache selbst zur Aufhebung des angefochtenen Entscheids (<ref-ruling> E. 4a S. 469; <ref-ruling> E. 2a S. 232, je mit Hinweisen). Nach der Rechtsprechung kann jedoch eine - nicht besonders schwerwiegende - Verletzung des Anspruches auf rechtliches Gehör in oberer Instanz geheilt werden, wenn dieser die gleiche bzw. eine nicht engere Überprüfungsbefugnis zusteht wie der Vorinstanz (vgl.
BGE 126 II 111 E. 6b/aa S. 123 f.; <ref-ruling> E. 2d S. 138; <ref-ruling> E. 3a S. 275 f.; <ref-ruling> E. 4 S. 87; <ref-ruling> E. 2 S. 95 f.). Vorliegend verfügte das Verwaltungsgericht über die gleiche umfassende Kognition wie die erste Instanz (vgl. § 52 Abs. 1 und 2 des Gesetzes über die Gerichtsorganisation des Kantons Solothurn vom 13. März 1977). Im Weiteren kann - wie das Verwaltungsgericht zu Recht angenommen hat - nicht von einer derart schwerwiegenden Gehörsverletzung gesprochen werden, welche eine Heilung ausschliessen würde. Wieso die Annahme einer Heilung vorliegend dennoch bundesrechts- bzw. verfassungswidrig sein sollte, ist nicht ersichtlich.
d) Der Beschwerdeführer bringt vor, der Beizug von Befragungsprotokollen aus dem Asylverfahren, welche durch die Fremdenpolizei des Kantons Aargau aufgenommen worden sind und sich bei deren Akten befunden haben, verstosse gegen das Datenschutzrecht des Bundes. Die entsprechenden Protokolle seien einzig zur Verwendung im Asylverfahren aufgenommen worden und ständen unter der Hoheit des Bundesamtes für Flüchtlinge, weshalb sie ohne dessen vorgängige Einwilligung nicht an die Fremdenpolizeibehörden des Kantons Solothurn hätten ediert werden dürfen.
Es fragt sich, ob mit Bezug auf die Weiterleitung von fremdenpolizeilich erstellten Asylakten zur Verwendung in einem ausländerrechtlichen Verfahren überhaupt von einem datenschutzrechtlich relevanten Vorgang gesprochen werden kann, geht es doch um amtliche Erhebungen, welche untereinander einen Zusammenhang haben. Die Herausgabe der fraglichen Protokolle durch die Fremdenpolizei des Kantons Aargau wäre aber auch unter diesem Aspekt nicht zu beanstanden. Das Bundesgesetz vom 19. Juni 1992 über den Datenschutz (DSG; SR 235. 1) sieht in Art. 19 Abs. 1 lit. a vor, dass Bundesorgane Personendaten bekannt geben dürfen, wenn die Daten für den Empfänger im Einzelfall zur Erfüllung seiner gesetzlichen Aufgabe unentbehrlich sind. Ob es sich bei einer kantonalen Fremdenpolizei, soweit sie mit Aufgaben des Asylrechts betraut ist, tatsächlich um eine Bundesbehörde im Sinne von Art. 2 Abs. 1 lit. b bzw. Art. 3 lit. h DSG handelt - welche als solche konsequenterweise auch selbständig nach Massgabe von Art. 19 Abs. 1 DSG über die Herausgabe der in ihrem Verantwortungsbereich befindlichen Akten zu bestimmen hätte -, wie das Bundesamt für Ausländerfragen in seiner Vernehmlassung annimmt, ist fraglich (vgl. <ref-ruling> E. 2d S. 156 mit Literaturzitaten; ferner: Urs Belser, in:
Kommentar zum schweizerischen Datenschutzgesetz, Basel/ Frankfurt a.M. 1995, N. 30 zu Art. 3), kann indessen offen bleiben, sehen doch auch die einschlägigen Weisungen des Regierungsrates des Kantons Aargau vom 9. November 1987 über die Bearbeitung von Personendaten in der Verwaltung (SAR 153. 151) für die Herausgabe von kantonalen Daten grundsätzlich die gleichen Voraussetzungen vor. Dass es sich bei Daten, welche über das Vorliegen einer Scheinehe Aufschluss geben können, um solche handelt, die zur Erfüllung der ausländerrechtlichen Aufgaben - wozu insbesondere die Prüfung der Voraussetzungen im Hinblick auf eine Bewilligungserteilung gehören - unentbehrlich sind, steht ausser Frage. Im Übrigen betreffen sowohl das Asylrecht als auch das Ausländerrecht letztlich die Frage der Anwesenheitsberechtigung von Ausländern in der Schweiz, weshalb nicht davon die Rede sein kann, die Daten würden - entgegen dem Grundsatz von Art. 4 Abs. 3 DSG - zu einem Zweck verwendet, welcher mit dem Zweck der ursprünglichen Datenerhebung nicht vereinbar wäre. Somit erscheinen die Einwendungen gegen den Beizug der Akten des Asylverfahrens bzw. der einschlägigen Befragungsprotokolle als nicht stichhaltig.
3.- a) Nach Art. 7 Abs. 2 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers dann keinen Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern und namentlich jene über die Begrenzung der Zahl der Ausländer zu umgehen.
Erfasst wird davon die sog. Scheinehe bzw. Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen (BGE <ref-ruling> E. 2 S. 294 ff.; <ref-ruling> E. 2 S. 2 ff., 97 E. 3 S. 101 ff.).
b) Dass Ehegatten mit der Heirat nicht eine eheliche Lebensgemeinschaft begründen, sondern die Vorschriften über Aufenthalt und Niederlassung von Ausländern umgehen wollen, entzieht sich in der Regel dem direkten Beweis und kann diesfalls, wie das früher bei der Bürgerrechtsehe zutraf (vgl. <ref-ruling>), nur durch Indizien nachgewiesen werden. Ein solches Indiz lässt sich darin erblicken, dass dem Ausländer die Wegweisung drohte, etwa weil er ohne Heirat keine Aufenthaltsbewilligung erhalten hätte oder sie ihm nicht verlängert worden wäre. Für das Vorliegen können sodann die Umstände und die kurze Dauer der Bekanntschaft sprechen sowie insbesondere die Tatsache, dass die Ehegatten eine Wohngemeinschaft gar nie aufgenommen haben. Dasselbe gilt, wenn für die Heirat eine Bezahlung vereinbart wurde.
Dass die Begründung einer wirklichen Lebensgemeinschaft gewollt war, kann umgekehrt nicht schon daraus abgeleitet werden, dass die Ehegatten während einer bestimmten Zeit zusammenlebten und intime Beziehungen unterhielten; ein derartiges Verhalten kann auch nur vorgespielt sein, um die Behörden zu täuschen (vgl. zum Ganzen BGE <ref-ruling> E. 2b S. 295 mit Hinweisen).
Für die Anwendbarkeit von Art. 7 Abs. 2 ANAG genügt es freilich nicht, dass die Ehe abgeschlossen wurde, um dem ausländischen Ehegatten den Aufenthalt in der Schweiz zu ermöglichen; erforderlich ist vielmehr, dass die eheliche Gemeinschaft nicht wirklich gewollt war. Auf die Motive der Heirat kommt es mit anderen Worten nicht an, sofern der Wille vorhanden ist, eine Lebensgemeinschaft zu begründen (<ref-ruling> E. 3b S. 102; vgl. <ref-ruling> E. 1b S. 5).
c) Die tatsächlichen Feststellungen des Verwaltungsgerichts und die daraus gezogenen Schlussfolgerungen lassen sich im Wesentlichen nicht beanstanden; die Vorinstanz kann sich auf verschiedene Indizien stützen, welche für das Vorliegen einer Ausländerrechtsehe sprechen.
Aus dem Sachverhalt ergibt sich, dass die Ehefrau des Beschwerdeführers bis zu ihrer Scheidung im November 1998 mit einem jugoslawischen Staatsangehörigen verheiratet war, mit dem sie erstmals 1991 in die Schweiz eingereist war und hier erfolglos um Asyl ersucht hatte. Im Januar 1999 kam sie zusammen mit ihrem geschiedenen Ehemann und ihren Töchtern erneut in die Schweiz und reichte ein weiteres Asylgesuch ein. Für die Dauer des Verfahrens wurde die Familie dem Kanton Aargau zugewiesen. Mit Verfügung vom 2. März 1999 trat das Bundesamt für Flüchtlinge auf das Asylgesuch nicht ein und verfügte die Wegweisung der ganzen Familie; als Ausreisefrist wurde damals der 15. April 1999 festgesetzt. Die Asylrekurskommission bestätigte diesen Entscheid mit Urteil vom 27. Mai 1999. Wegen fehlender Reisedokumente konnte die Wegweisung durch die Fremdenpolizei des Kantons Aargau indessen nicht vollzogen werden. Am 15. Mai 1999 war das geschiedene Ehepaar S._ zusammen mit den fünf Kindern nach Sarmenstorf AG gezogen, wo die Familie durch die öffentliche Fürsorge unterstützt wird. An dieser Situation hat sich - auch nach der Heirat von J.S._ mit dem Beschwerdeführer am 16. August 1999 - grundsätzlich nichts geändert. Entsprechende Ersuchen seitens des Rechtsvertreters des Beschwerdeführers beim Amt für öffentliche Sicherheit des Kantons Solothurn, bei der Gemeinde Sarmenstorf sowie beim Bundesamt für Flüchtlinge, der Ehefrau sowie deren Kindern in Abweichung zur ursprünglichen Kantonszuweisung die Wohnsitznahme beim Beschwerdeführer im Kanton Solothurn zu gestatten, wurden abschlägig beantwortet.
Zunächst erblickt das Verwaltungsgericht ein Indiz für das Vorliegen einer Scheinehe darin, dass die Heirat die einzige Möglichkeit für die Ehefrau des Beschwerdeführers darstellte, um in den Besitz einer Aufenthaltsbewilligung zu gelangen und damit der Wegweisung zu entgehen. Dem hält der Beschwerdeführer entgegen, das Verkündgesuch sei am 14. Mai 1999 und damit bereits vor Eröffnung des letztinstanzlichen Asylentscheids der Asylrekurskommission gestellt worden, weshalb der Eheschluss gerade nicht Folge der Beschwerdeablehnung sein könne. Dieser Einwand ist unbehelflich: Bereits das Bundesamt für Flüchtlinge hatte in seinem Nichteintretens- und Wegweisungsentscheid vom 2. März 1999 einer allfälligen Beschwerde die aufschiebende Wirkung entzogen und die Asylrekurskommission lehnte die Wiederherstellung derselben mit Verfügung vom 12. April 1999 ab. Der Ehefrau des Beschwerdeführers hat der Vollzug der Wegweisung folglich im Zeitpunkt der Einreichung des Verkündgesuchs bereits gedroht.
Dass sich die Ehefrau - wie der Beschwerdeführer vorbringt - auch ohne Heirat noch während längerer Zeit in der Schweiz hätte aufhalten können, ist nicht erhärtet und im Übrigen auch irrelevant. Sodann ist nicht zu beanstanden, wenn das Verwaltungsgericht im Umstand, dass der Beschwerdeführer zwölf Jahre jünger ist als seine Ehefrau, mit ein Indiz für das Vorliegen einer Scheinehe erblickt. Zwar mag es zutreffen, dass auch Ehen, bei denen die Partner altersmässig noch weiter auseinander liegen, tatsächlich gelebt werden. Im Allgemeinen bilden jedoch solche Ehen, bei denen die Ehefrau bedeutend älter ist als der Ehemann, die Ausnahme, weshalb ein entsprechender Altersunterschied ein - wenn auch nicht für sich allein ausschlaggebendes, so doch in Verbindung mit anderen Anzeichen - taugliches Indiz dafür darstellt, dass die Ehe zur Umgehung von ausländerrechtlichen Vorschriften eingegangen worden ist. Von einem Verstoss gegen <ref-law> - wie vom Beschwerdeführer in diesem Zusammenhang geltend gemacht - kann keine Rede sein. Ebenso wenig zu Kritik Anlass gibt die durch die Vorinstanz vorgenommene Würdigung der kurzen Bekanntschaftszeit des Beschwerdeführers mit seiner Ehefrau vor der Heirat von bloss rund drei Monaten. Stark ins Gewicht fällt, dass die Ehefrau auch nach der Heirat weiterhin mit ihrem kurz zuvor geschiedenen und nach wie vor in die Familiengemeinschaft integrierten früheren Ehemann zusammen wohnt. Anlässlich einer Befragung im Rahmen des Asylverfahrens vom 15. Februar 1999 - drei Monate vor Einreichung des Verkündgesuchs - hat sie denn auch zu Protokoll gegeben, sie und ihr geschiedener Ehemann seien wieder zusammen und beabsichtigten, erneut zu heiraten. Auf dieser unter Hinweis auf die Wahrheits- und Mitwirkungspflicht gemachten Aussage, für deren Richtigkeit nicht zuletzt die erwähnte Wohnsituation der vormaligen Ehegatten spricht, ist die Ehefrau des Beschwerdeführers zu behaften. Dass es sich dabei um eine blosse Schutzbehauptung im Asylverfahren gehandelt haben soll, wie der Beschwerdeführer glauben machen will, ist nicht belegt; jedenfalls deckt sich die fragliche Aussage mit der von der Tochter A._ gemachten Aussage. Was die Wohnsituation des Beschwerdeführers und seiner Ehefrau anbelangt, so trifft zu, dass der im Kanton Aargau lebenden Ehefrau der Zuzug zum Ehemann in den Kanton Solothurn aufgrund der für sie (auch als abgewiesene Asylsuchende) weiterhin geltenden Kantonszuteilung und infolge der bei einem Wegzug drohenden Streichung der Fürsorgeleistungen durch die Gemeinde Sarmenstorf praktisch verunmöglicht war. Es bleibt jedoch die Tatsache, dass der Beschwerdeführer und seine Ehefrau nie zusammengelebt haben. Daran vermögen auch allfällige regelmässige Besuche der Ehefrau beim Beschwerdeführer, soweit sie tatsächlich stattgefunden haben, nichts zu ändern. Dass der Beschwerdeführer seine Ehefrau als Köchin schätzen gelernt hat und selber möglicherweise bereit wäre, mit ihr zusammenzuleben, vermag die aus den übrigen Umständen sich aufdrängende Schlussfolgerung, Ziel des ausländischen Ehepartners sei nicht die Führung einer Lebensgemeinschaft mit dem Beschwerdeführer, sondern nur der mit der Ehe verbundene fremdenpolizeiliche Status, nicht zu widerlegen. Es handelt sich jedenfalls aus der Sicht des ausländischen Ehepartners, auf die es nach der Rechtsprechung (primär) ankommt (unveröffentlichte Urteile vom 16. März 2000 i.S. Baran, E. 3b, sowie vom 27. August 1999 i.S. Demi, E. 2b), um eine Scheinehe. Die Verweigerung der Aufenthaltsbewilligung für die Ehefrau und deren vier minderjährige Kinder verstösst somit nicht gegen Bundesrecht.
d) Der Beschwerdeführer kann auch aus dem in Art. 8 Ziff. 1 EMRK garantierten Anspruch auf Achtung des Familienlebens bzw. der entsprechenden Garantie von <ref-law> (vgl. <ref-ruling> E. 7 S. 394) nichts zu seinen Gunsten ableiten, fehlt es doch bei einer Scheinehe an einer intakten familiären Beziehung, welche den Schutz dieses Grundrechts geniesst (unveröffentlichtes Urteil vom 28. August 1995 i.S. Kilinc, E. 3b).
4.- Zu beurteilen bleibt die mitangefochtene Festsetzung des armenrechtlichen Honorars bzw. der Parteientschädigung im Verfahren vor Verwaltungsgericht.
a) Der Beschwerdeführer bringt vor, das Verwaltungsgericht habe zwar das Gesuch um Gewährung der unentgeltlichen Rechtspflege gutgeheissen, es habe aber die Kostennote seines Anwalts zu Unrecht gekürzt, ohne diesem hiezu vorgängig das rechtliche Gehör gewährt zu haben.
Nach der bundesgerichtlichen Rechtsprechung kommt den Kantonen bei der Bemessung des Honorars eines amtlichen Rechtsvertreters ein weiter Ermessensspielraum zu, was insbesondere für die Beurteilung der Angemessenheit anwaltlicher Bemühungen gilt. In Fällen, in denen eine kantonale Behörde den vom Anwalt in Rechnung gestellten Arbeitsaufwand als übersetzt bezeichnet, schreitet das Bundesgericht aufgrund des bundesverfassungsrechtlichen Anspruches auf unentgeltliche Rechtspflege (<ref-law>, vormals abgeleitet aus Art. 4 Abs. 1 aBV) nur ein, wenn der Ermessensspielraum klarerweise überschritten worden ist und Bemühungen nicht honoriert werden, die zweifelsfrei zu den Obliegenheiten eines amtlichen Vertreters gehören (<ref-ruling> E. 2b/d S. 134/136 mit Hinweisen). Das Verwaltungsgericht hat beim streitigen Kostenspruch jenen Aufwand unberücksichtigt gelassen, welcher auf Interventionen des Rechtsbeistandes des Beschwerdeführers bei verschiedenen Stellen im Zusammenhang mit der Kantonszuteilung zurückzuführen ist. Die Auffassung des Verwaltungsgerichts, diese Interventionen beträfen nicht den Gegenstand des Beschwerdeverfahrens und seien aus diesem Grund honorarmässig nicht zu veranschlagen, stellt jedenfalls keine Ermessensüberschreitung dar und ist daher nicht zu beanstanden. Im Übrigen liegt im blossen Umstand, dass das Verwaltungsgericht nicht den in der Honorarnote festgehaltenen Betrag zugesprochen und insofern "die Honorarnote gekürzt" hat, keine Verletzung des rechtlichen Gehörs. So hat das Bundesgericht die Festsetzung des Honorars nach Ermessen unter Abweichung von einer ungenügend spezifizierten Honorarnote ohne vorherige Anhörung des betroffenen Anwalts als zulässig erachtet und ausgeführt, aus dem Anspruch auf rechtliches Gehör könne jedenfalls keine allgemeine, in jedem Fall zu beachtende Pflicht des Richters abgeleitet werden, der Partei oder ihrem Anwalt Gelegenheit zur nachträglichen Substantiierung zu geben; namentlich könnten einem solchen Vorgehen Interessen der Rechtspflege (Verzögerung des ordnungsgemässen Gangs des Verfahrens, unverhältnismässiger Aufwand) entgegenstehen (unveröffentlichtes Urteil vom 2. September 1994 i.S. Saluz, E. 4; vgl. auch Albertini, a.a.O., S. 328). Vorliegend scheint der Verzicht auf die Anhörung des Anwalts zum Kostenpunkt vertretbar, da eine solche in einem schriftlichen Verfahren zu einer merklichen Verzögerung geführt hätte.
b) Der Beschwerdeführer macht sodann geltend, das Verwaltungsgericht habe zur Bemessung der - nebst dem armenrechtlichen Honorar zusätzlich zugesprochenen - Parteientschädigung unzulässigerweise ebenfalls auf den armenrechtlichen Honoraransatz abgestellt. Aufgrund welcher kantonalen Vorschrift das Verwaltungsgericht verpflichtet gewesen wäre, die Parteientschädigung höher als auf Fr. 600.-- festzusetzen, wird in der Beschwerdeschrift nicht dargetan. Der blosse Einwand, das Verwaltungsgericht habe für die Parteientschädigung nicht den üblichen Normalansatz von Fr. 200.-- pro Stunde, sondern den tieferen armenrechtlichen Ansatz verwendet, vermag sich auf keine entsprechende Berechnung zu stützen. Das Gericht legte vielmehr nach Ermessen eine Pauschalsumme von Fr. 1'800.-- fest, die es zum Teil als Armenrechtshonorar (Fr. 1'200.--) und zum Teil als Parteientschädigung (Fr. 600.--) bezeichnete. Inwiefern dieses Vorgehen unzulässig sein soll, ist nicht ersichtlich.
5.- a) Nach dem Gesagten ist die Verwaltungsgerichtsbeschwerde als unbegründet abzuweisen.
b) Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 in Verbindung mit Art. 153 und Art. 153a OG). Zu prüfen ist das für das bundesgerichtliche Verfahren gestellte Gesuch um unentgeltliche Rechtspflege und Verbeiständung (Art. 152 OG). Der Beschwerdeführer gibt an, bloss temporär zu arbeiten und nicht in der Lage zu sein, mehr als Fr. 2'300.-- netto zu verdienen, weshalb eine teilweise Unterstützung durch die Fürsorge unvermeidlich sei. Gemäss Eingabe vom 13. Dezember 2000 hat er einen Arbeitsunfall erlitten, was seine angespannte finanzielle Lage noch verschärfen dürfte. Die Bedürftigkeit des Beschwerdeführers ist damit als ausgewiesen anzusehen. Die von ihm gestellten Rechtsbegehren können nicht als zum Vornherein aussichtslos bezeichnet werden, bedurfte doch ein Teil der aufgeworfenen formellen Fragen einer eingehenderen Prüfung. Es rechtfertigt sich insofern, dem Gesuch um unentgeltliche Prozessführung und Verbeiständung zu entsprechen.
Damit sind keine Kosten zu erheben (Art. 152 Abs. 1 OG) und der Rechtsvertreter des Beschwerdeführers ist für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse zu entschädigen (Art. 152 Abs. 2 OG). Bei der Bemessung des Anwaltshonorars ist allerdings dem Umstand Rechnung zu tragen, dass die Beschwerde in materieller Hinsicht keine Erfolgsaussichten haben konnte.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt.
a) Es werden keine Kosten erhoben.
b) Fürsprech Jürg Walker, Solothurnerstrasse 101, Olten, wird als amtlicher Vertreter des Beschwerdeführers bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse ein Honorar von Fr. 1'000.-- ausgerichtet.
3.- Dieses Urteil wird dem Beschwerdeführer, dem Amt für öffentliche Sicherheit (Abteilung Ausländerfragen) und dem Verwaltungsgericht des Kantons Solothurn sowie dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 13. Februar 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident: Der Gerichtsschreiber: