Erwägungen:
1. 1.1 X._, Serbe, geb. 1975, reiste erstmals im Oktober 1992 in die Schweiz ein. Sein Asylgesuch wurde am 17. Februar 1993 abgewiesen, wobei das Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) wegen des damals unzumutbaren Vollzugs der Wegweisung die vorläufige Aufnahme von X._ und der damaligen Lebenspartnerin und des gemeinsamen Kindes anordnete. Der nach Aufhebung der gruppenweisen vorläufigen Aufnahme zuletzt von der Schweizerischen Asylrekurskommission auf Ende November 1999 angesetzten Ausreisefrist wurde keine Folge geleistet. Im Rahmen der "humanitären Aktion 2000" wurden X._, seine damalige Lebenspartnerin und die mittlerweile zwei gemeinsamen Kinder erneut vorläufig aufgenommen. Ein Gesuch um Erteilung der Aufenthaltsbewilligung von X._ wies das Amt für Migration des Kantons Luzern am 28. Juli 2003 wegen eines Strafbefehls (45 Tage Gefängnis bedingt und Fr. 800.-- Busse wegen Gebrauchs gefälschter fremdenpolizeilicher Ausweispapiere) und mangels gefestigter Arbeitsstelle ab. Am 19. Mai 2004 sodann hob das Bundesamt für Flüchtlinge die vorläufige Aufnahme von X._ auf und ordnete die sofort vollziehbare Wegweisung aus; Grund waren zwei laufende Strafverfahren (im Fürstentum Liechtenstein wegen Verdachts auf Freiheitsberaubung und Raub [eingestellt am 28. November 2006] sowie in den Kantonen Luzern und Uri wegen verschiedener Einbruchdiebstähle). Das Bundesamt für Zuwanderung, Integration und Auswanderung (heute: Bundesamt für Migration) erliess am 9. Juli 2004 angesichts der gerichtlichen Verurteilung (Ausweisfälschung) und der laufenden Strafverfahren eine bis 11. Juli 2014 gültige Einreisesperre. Im Oktober 2004 reiste X._ nach Novi Pazar, Serbien, zurück. Er lebte dort während rund zwei Jahren mit seiner Freundin Y._, einer aus Bosnien-Herzegowina stammenden Schweizer Bürgerin, zusammen. Am 26. Oktober 2006 heiratete er sie in Belgrad.
Am 14. Mai 2007 reiste X._ wieder in die Schweiz ein und stellte ein zweites Asylgesuch, auf welches das Bundesamt für Migration am 19. Juli 2007 nicht eintrat (bestätigt durch Urteil des Bundesverwaltungsgerichts vom 27. August 2007).
1.2 Am 16. August 2007 stellte Y._ beim Amt für Migration des Kantons Luzern ein Gesuch um Familiennachzug für ihren Ehemann X._. Das Amt sistierte das Bewilligungsverfahren im Hinblick auf das noch hängige Strafverfahren wegen Diebstahls und wies X._, unter Ansetzung einer Ausreisefrist, aus dem Kanton Luzern weg. Mit Urteil vom 23. Mai 2008 wies das Verwaltungsgericht des Kantons Luzern die gegen die entsprechende Verfügung vom 14. September 2007 erhobene Beschwerde ab, soweit es darauf eintrat; das Amt für Migration wurde angewiesen, X._ eine neue Ausreisefrist anzusetzen.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 30. Juni 2008 beantragen X._ und Y._ dem Bundesgericht, das Amt für Migration sei anzuweisen, X._ in Abänderung der angefochtenen Verfügung eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau zu erteilen.
Es ist weder ein Schriftenwechsel noch sind andere Instruktionsmassnahmen angeordnet worden.
2. 2.1 Angefochten ist ein Urteil, das eine Zwischenverfügung zum Gegenstand hat (Sistierung des Bewilligungsverfahrens, Verweigerung der Landesanwesenheit während dessen Hängigkeit [Wegweisung]). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist zur Anfechtung eines Zwischenentscheids, der nicht die Zuständigkeit oder Ausstandsfragen betrifft (vgl. Art. 92 BGG), nur zulässig, wenn sie einerseits gegen den Endentscheid zulässig sein wird und wenn andererseits die Voraussetzungen von Art. 93 BGG erfüllt sind.
2.1.1 Im Hauptverfahren streitig ist die Erteilung einer Aufenthaltsbewilligung, auf die der mit einer Schweizerin verheiratete Beschwerdeführer im Grundsatz Anspruch hat, sodass weder Art. 83 lit. c Ziff. 2 BGG noch sonst ein Ausschlussgrund zum Tragen kommt. Sodann kann das angefochtene Urteil für die Beschwerdeführer insofern einen nicht wieder gutzumachenden Nachteil bewirken (vgl. Art. 93 Abs. 1 lit. a BGG), als sie ihre Ehe vorläufig nicht in der Schweiz leben können. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist insofern zulässig.
2.1.2 Das angefochtene Urteil stützt sich ausschliesslich auf kantonales (Verfahrens-)Recht. Vor Bundesgericht kann nicht unmittelbar die Verletzung kantonalen Rechts gerügt werden. Vielmehr muss geltend gemacht werden, dass die kantonalen Behörden bei dessen Anwendung schweizerisches Recht im Sinne von Art. 95 BGG verletzt haben. In Frage kommen vorliegend Bundes(verfassungs)recht, Völkerrecht und kantonale verfassungsmässige Rechte. Dabei prüft das Bundesgericht, was verfassungsmässige Rechte betrifft, den angefochtenen Entscheid nur insoweit, als entsprechende Rechtsverletzungen spezifisch dargelegt werden (Art. 106 Abs. 2 in Verbindung mit Art. 42 Abs. 2 BGG). Vorliegend ist, da das Hauptanliegen der Beschwerdeführer an sich darin besteht, X._ müsse vorerst und jedenfalls bis zum Abschluss des Bewilligungsverfahrens im Land bleiben können, im Ergebnis eine vorsorgliche Massnahme (Vollzugsstopp betreffend Wegweisung) streitig, sodass sich die Beschränkung der Beschwerdegründe auch aus Art. 98 BGG ergibt.
2.2 Die Beschwerdeführer rügen eine Verletzung von Art. 8 EMRK. Sie tun dies weitgehend in einer Weise, wie sie dies im Rahmen einer Beschwerde gegen den die Aufenthaltsbewilligung verweigernden Endentscheid tun könnten. Insofern tragen ihre Rügen dem beschränkten Gegenstand der vorliegenden Beschwerde nur zum Teil Rechnung (Recht- bzw. Verfassungsmässigsmässigkeit der getroffenen verfahrensrechtlichen Anordnungen).
2.3 Nicht näher substantiiert und ohnehin offensichtlich unbegründet ist zunächst die Behauptung (s. Beschwerdeschrift S. 6 am Ende), Art. 8 EMRK lasse es nicht zu, den Ausländer zu verpflichten, den materiellen Entscheid über die Aufenthaltsbewilligung im Ausland abzuwarten (vgl. dazu Urteil 2C_11/2007 vom 21. Juni 2007 E. 2.3.3). Offensichtlich unbegründet ist sodann die Rüge, für die Verfahrenssistierung bzw. die vorläufige Wegweisung fehle es an einer gesetzlichen Grundlage. § 41 des Luzerner Gesetzes vom 3. Juli 1972 über die Verwaltungsrechtspflege (VRG) bzw. Art. 1a ANAG und Art. 1 ANAV, ferner auch ganz allgemein § 45 VRG ermächtigen das Amt für Migration zu den umstrittenen getroffenen verfahrensleitenden Anordnungen. Nicht nachvollziehbar ist sodann die Rüge der Gehörsverweigerung durch angeblich fehlende Begründung; dem angefochtenen Urteil ist klar und nachvollziehbar zu entnehmen, aus welchen Gründen das Verwaltungsgericht die Anordnungen des Amtes für Migration als rechtmässig erachtet. Zu prüfen bleibt, ob die Verfahrenssistierung und die damit verbundene Ausreiseverpflichtung sonstwie - inhaltlich - gegen den Beschwerdeführern zustehende verfassungsmässige Rechte verstossen.
2.4 2.4.1 Gemäss § 41 VRG kann die Behörde das Verfahren aus Gründen der Zweckmässigkeit aussetzen, namentlich wenn ihr Entscheid von einem anderen abhängt oder wesentlich beeinflusst wird. Dass der zuständigen Behörde bei einem solchen Entscheid, wie das Verwaltungsgericht darlegt, grosses Ermessen zusteht, liegt auf der Hand. Dasselbe gilt beim Erlass vorsorglicher Verfügungen im Sinne von § 45 VRG. Was insbesondere letztere betrifft, so ergehen sie aufgrund einer bloss provisorischen Prüfung der Sach- und Rechtslage. Erforderlich ist eine Interessenabwägung, wofür die Behörde nicht gehalten ist, zeitraubende Abklärungen zu treffen; vielmehr kann sie sich mit einer summarischen Beurteilung der Situation aufgrund der ihr zur Verfügung stehenden Akten begnügen (vgl. BGE 130 II 149 E. 2.2 S.155; 129 II 286 E. 3 S. 289; 127 II 132 E. 3 S. 137 f.; 117 V 185 E. 2b S. 191, je mit Hinweisen). Auf Beschwerde hin kann das Bundesgericht entsprechende verfahrensleitende Anordnungen nur aufheben, wenn die Behörde wesentliche Interessen und wichtige Gesichtspunkte ausser Acht gelassen oder offensichtlich falsch bewertet haben sollte und die von ihr vorgenommene Interessenabwägung jeglicher vernünftigen Grundlage entbehrte (vgl. BGE 129 II 286 E. 3 S. 289; Urteil 2C_11/2007 vom 21. Juni 2007 E. 2.3.2 mit Hinweisen).
2.4.2 Die Zweckmässigkeit der Sistierung des Bewilligungsverfahrens liegt vorliegend auf der Hand. Der Beschwerdeführer hat zwar gestützt auf Art. 8 EMRK einen Anspruch auf Erteilung der Aufenthaltsbewilligung. Nach der Aktenlage ist indessen nicht gewiss, ob ihm eine solche erteilt werden muss, wenn es im Strafverfahren betreffend verschiedene Einbruchdiebstähle zu einer Verurteilung kommen sollte. Insbesondere kommt im Falle des Beschwerdeführes der sog. Zweijahresregel bei der Interessenabwägung gemäss Art. 8 Ziff. 2 EMRK angesichts der weiteren Umstände nicht die gleiche Bedeutung zu wie in anderen Fällen. Er ist bereits früher straffällig geworden, hat mehrfach fremdenpolizeiliche Anordnungen missachtet (zuletzt Einreise trotz Einreisesperre und Stellung eines untauglichen Asylgesuchs), und zudem bis vor relativ kurzer Zeit die Beziehung mit der Beschwerdeführerin, seiner heutigen Ehefrau, während rund zwei Jahren in seiner Heimat gelebt, welche ihn im Wissen um die prekäre ausländerrechtliche Situation geheiratet hat. Ein definitiver Entscheid über das Nachzugsgesuch vor Abschluss des Strafverfahrens erscheint nicht geboten. Dass die Verfahrenssistierung bei dieser Konstellation nicht die Unschuldsvermutung verletzt, bedarf, auch angesichts der diesbezüglich bloss rudimentären Ausführungen in der Beschwerdeschrift, keiner näheren Erläuterung. Der Sistierungsentscheid verstösst in keiner Weise gegen verfassungsmässige Rechte der Beschwerdeführer.
Dieselben Überlegungen sind von Belang in Bezug auf die Anordnung, dem in Missachtung einer rechtskräftigen Einreisesperre und damit unrechtmässig eingereisten Beschwerdeführer (vgl. Art. 1 ANAV) während der Hängigkeit des (sistierten) Bewilligungsverfahrens die Anwesenheit in der Schweiz zu verweigern; die entsprechende Massnahme hält der im dargelegten Sinne beschränkten bundesgerichtlichen Prüfung grundsätzlich stand. Auch die Hängigkeit eines Strafverfahrens ist dabei insofern nicht von entscheidender Bedeutung, als der Beschwerdeführer für eine wirksame Verteidigung nicht darauf angewiesen ist, sich dauernd in der Schweiz aufzuhalten; die Beschwerdeführer machen dies in ihrer Beschwerdebegründung denn auch nicht etwa geltend.
2.5 Eine Besonderheit liegt darin, dass die Sistierung des Bewilligungsverfahrens hier mit der (vorsorglichen) Wegweisung des Beschwerdeführers verknüpft ist. Damit droht dessen als solche grundsätzlich nicht zu beanstandende vorläufige Fernhaltung aus der Schweiz, welche die Gestaltung des Ehelebens der Beschwerdeführer beeinflusst, länger zu dauern als bei einem wie üblich laufenden Bewilligungsverfahren. Zum heutigen Zeitpunkt stellt sich jedoch die Frage einer Rechtsverzögerung nicht ernsthaft. Die diesbezüglich rudimentären Vorbringen in der Beschwerdeschrift gebieten keine näheren Erwägungen darüber, ob und wann bei zunehmender Dauer des Strafverfahrens unter dem Gesichtswinkel von Art. 29 Abs. 1 BV allenfalls eine Wiederaufnahme des Bewilligungsverfahrens oder die Erteilung einer Wiedereinreisebewilligung an den Beschwerdeführer in Betracht zu ziehen wäre.
2.6 Die Beschwerde erweist sich, soweit darauf eingetreten werden kann, als offensichtlich unbegründet (Art. 109 Abs. 2 lit. a BGG), und sie ist im vereinfachten Verfahren gemäss Art. 109 BGG abzuweisen.
Mit diesem Urteil wird das in der Beschwerdeschrift gestellte Gesuch, dem Beschwerdeführer sei für die Dauer des Beschwerdeverfahrens im Sinne einer vorsorglichen Massnahme der weitere Aufenthalt im Kanton Luzern zu bewilligen, gegenstandslos.
2.7 Dem Verfahrensausgang entsprechend sind die Gerichtskosten (Art. 65 BGG) den Beschwerdeführern zu gleichen Teilen unter solidarischer Haftung aufzuerlegen (Art. 66 Abs. 1 Satz 1 und Abs. 5 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern je zur Hälfte unter solidarischer Haftung auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, dem Amt für Migration und dem Verwaltungsgericht des Kantons Luzern sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 8. August 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Feller