Sachverhalt:
A. Der aus Mazedonien stammende X._, geb. 1982, reiste am 8. Mai 1988 zusammen mit seiner Mutter und seinem Bruder in die Schweiz ein. Am 14. November 1991 wurde er in die Niederlassungsbewilligung seines Vaters einbezogen.
Mit Verfügung des Bezirksinspektorats I Wolhusen vom 22. Januar 1999 wurde X._ wegen ungebührlichen Verhaltens frühzeitig aus der obligatorischen Schulpflicht entlassen. Am 6. August 2001 verwarnte ihn das Amt für Migration des Kantons Luzern wegen diverser Strafverfügungen der Jugendanwaltschaft.
Nachdem X._ als junger Erwachsener bereits verschiedentlich wegen geringfügigerer Delikte verurteilt worden war, sprach ihn das Kriminalgericht des Kantons Luzern mit Urteil vom 19. November 2004 des mehrfachen, qualifiziert begangenen Raubes, einfachen bandenmässigen Diebstahls, der mehrfachen Sachbeschädigung und mehrfachen Erpressung schuldig und wies ihn in eine Arbeitserziehungsanstalt ein. In den Jahren 2005 und 2006 ergingen weitere Strafverfügungen gegen ihn; so wurde er unter anderem am 24. Oktober 2005 wegen Veruntreuung zu einer unbedingten Gefängnisstrafe von fünf Wochen und einer Geldbusse von Fr. 400.-- verurteilt.
B. Mit Verfügung vom 24. September 2007 wies das Amt für Migration des Kantons Luzern X._ mit Blick auf das Strafurteil vom 19. November 2004 sowie die weiteren zahlreichen Verurteilungen auf unbestimmte Zeit aus der Schweiz aus.
Mit Entscheid vom 1. Oktober 2008 hob das Justiz- und Sicherheitsdepartement des Kantons Luzern, Vollzugs- und Bewährungsdienste, den Vollzug der Arbeitserziehungsmassnahme wegen Aussichtslosigkeit ihrer Fortführung auf. Mit Urteil vom 14. Juli 2009 sollte das Obergericht des Kantons Luzern (als Appellationsinstanz) die anstelle dieser Massnahme auszufällende Freiheitsstrafe auf drei Jahre und drei Monate festlegen (unter Anrechnung von Polizei- und Untersuchungshaft sowie der im Massnahmenvollzug verbrachten Tage) und weitere zugunsten der Arbeitserziehungsmassnahme aufgeschobene Freiheitsstrafen (von insgesamt gut sechs Wochen) für vollziehbar erklären.
C. Am 8. Januar 2009 wies das Verwaltungsgericht des Kantons Luzern, Verwaltungsrechtliche Abteilung, eine dagegen gerichtete Beschwerde von X._ ab.
D. Mit Eingabe vom 16. Februar 2009 erhebt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, das Urteil des Verwaltungsgerichts vom 8. Januar 2009 aufzuheben und sein Gesuch "um Erneuerung der Niederlassungsbewilligung" gutzuheissen. Im Übrigen wird um unentgeltliche Rechtspflege und Verbeiständung für das Verfahren vor Bundesgericht ersucht.
Das Amt für Migration und das Verwaltungsgericht des Kantons Luzern sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
E. Dem vom Beschwerdeführer gestellten Gesuch um aufschiebende Wirkung wurde mit Verfügung des Präsidenten der II. öffentlich-rechtlichen Abteilung vom 19. Februar 2009 entsprochen.
F. Mit Eingabe vom 20. Mai 2009 lässt der Beschwerdeführer beim Bundesgericht weitere Beweismittel einreichen.

Erwägungen:
1. 1.1 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid über eine gestützt auf Art. 10 Abs. 1 lit. a des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG) verfügte Ausweisung, wogegen das ordentliche Rechtsmittel der Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist (<ref-law> e contrario). Der Beschwerdeführer ist hierzu legitimiert (<ref-law>).
1.2 Zwar ist am 1. Januar 2008 das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG, SR 142.20) in Kraft getreten. Praxisgemäss bleibt indessen, in analoger Anwendung von Art. 126 Abs. 1 AuG, das bisherige Recht anwendbar, wenn - wie hier - ein Ausweisungsverfahren noch vor Inkrafttreten des neuen Rechts eröffnet worden ist (vgl. Urteile 2C_745/2008 vom 24. Februar 2009, E. 1.2.2-1.2.4, und 2C_701/2008 vom 26. Februar 2009, E. 2).
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG; vgl. <ref-ruling> E. 2.1 S. 245 f.), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254).
Eine qualifizierte Rügepflicht gilt u.a. hinsichtlich der Verletzung von Grundrechten. Das Bundesgericht prüft solche Rügen nur, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 1.4 S. 287).
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>; vgl. <ref-ruling> E. 1.5 S. 146 f.).
2. 2.1 Die Niederlassungsbewilligung erlischt mit der Ausweisung (Art. 9 Abs. 3 lit. b ANAG). Gemäss Art. 10 Abs. 1 ANAG kann ein Ausländer unter anderem dann aus der Schweiz oder aus einem Kanton ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde (lit. a) oder wenn sein Verhalten im Allgemeinen und seine Handlungen darauf schliessen lassen, dass er nicht gewillt oder nicht fähig ist, sich in die im Gaststaat geltende Ordnung einzufügen (lit. b).
Der Beschwerdeführer wurde mit Urteil des Luzerner Kriminalgerichts vom 19. November 2004 des mehrfachen, qualifiziert begangenen Raubes, einfachen bandenmässigen Diebstahls, der mehrfachen Sachbeschädigung und mehrfachen Erpressung schuldig erklärt und deswegen in eine Arbeitserziehungsanstalt eingewiesen. Damit ist der Ausweisungsgrund von Art. 10 Abs. 1 lit. a ANAG erfüllt. Dieser kommt nach der Rechtsprechung auch dann zum Tragen, wenn anstelle einer Strafe die (als monistische Massnahme ausgestaltete) Einweisung eines jungen Erwachsenen in eine Arbeitserziehungsanstalt gemäss dem früheren <ref-law> (in der bis zum 31. Dezember 2006 gültigen Fassung vom 18. März 1971; AS 1971 777) angeordnet wurde, da der genannte Ausweisungsgrund allein auf das Vorliegen eines Schuldspruches wegen eines Verbrechens oder Vergehens abstellt, unabhängig von der Art der jeweils ausgesprochenen Sanktion (eingehend: <ref-ruling> E. 3 S. 524 ff.).
Mit Blick auf die vom Beschwerdeführer begangenen zahlreichen übrigen, im Vergleich dazu weniger schwerwiegenden Gesetzesverstösse, welche zu weiteren strafrechtlichen Verurteilungen führten, muss vorliegend zudem auch der Ausweisungsgrund von Art. 10 Abs. 1 lit. b ANAG als erfüllt betrachtet werden.
2.2 Die Ausweisung soll nach Art. 11 Abs. 3 ANAG nur verfügt werden, wenn sie nach den gesamten Umständen angemessen erscheint. Für die Beurteilung der Angemessenheit, d.h. der Verhältnismässigkeit (vgl. <ref-ruling> E. 2a S. 523) der Ausweisung erklärt Art. 16 Abs. 3 der Vollziehungsverordnung vom 1. März 1949 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer (ANAV) namentlich als wichtig die Schwere des Verschuldens des Ausländers, die Dauer seiner Anwesenheit in der Schweiz und die ihm und seiner Familie drohenden Nachteile. Da bei der vorzunehmenden Interessenabwägung die persönlichen und familiären Verhältnisse zu berücksichtigen sind, hält eine im Sinne von Art. 11 Abs. 3 ANAG verhältnismässige Ausweisung grundsätzlich auch vor Art. 8 EMRK bzw. <ref-law> (Recht auf Achtung des Privat- und Familienlebens) stand.
2.3 Die kantonalen Behörden haben die für die Beurteilung der Verhältnismässigkeit der Ausweisung relevanten Kriterien zutreffend dargelegt. Der Beschwerdeführer wurde wegen mehrfachen, qualifiziert begangenen Raubes, einfachen bandenmässigen Diebstahls, mehrfacher Sachbeschädigung und mehrfacher Erpressung verurteilt. Gemäss dem Strafurteil vom 19. November 2004 hatte die Tätergruppe, zu deren Kern der Beschwerdeführer und drei seiner Kollegen gehörten, zahlreiche Raubtaten und Diebstähle (zum Teil verbunden mit Sachbeschädigungen) begangen, zu denen sie sich jeweils entschlossen haben sollen, wenn sie kein Geld gehabt hätten. Bei den Raubtaten führten sie eine als gefährliche Waffe zu qualifizierende Stahlrute mit, welche sie in zwei Fällen auch gegenüber einem Opfer (als Würge- bzw. Schlaginstrument) einsetzten. Diese Vorgehensweise wird im Strafurteil als "hinterlistig, brutal und skrupellos" und von ihrem Unrechts- und Schuldgehalt besonders schwer wiegend bezeichnet. Da der Beschwerdeführer die erwähnten Straftaten als junger Erwachsener mit 19 Jahren begangen hatte, wurde er in eine Arbeitserziehungsanstalt eingewiesen. Das Kriminalgericht erachtete das Risiko eines Rückfalles bei Verzicht auf diese Massnahme als hoch. Rechtfertigungsgründe bzw. Schuldausschluss- oder -milderungsgründe lagen keine vor. In fremdenpolizeilicher Hinsicht ist insofern von einem schweren Verschulden auszugehen. Hinzu kommt, dass der Beschwerdeführer - abgesehen von den erwähnten Straftaten - in den Jahren 1995 bis 2005 17 weitere Strafurteile bzw. Strafverfügungen erwirkt hat, darunter solche wegen einfacher Körperverletzung, Drohung, Gewalt und Drohung gegen Beamte, Hehlerei und Veruntreuung. Die anhaltende Straffälligkeit zeugt von einer nicht hinnehmbaren Gleichgültigkeit gegenüber der geltenden Rechtsordnung. Bedenklich mutet an, dass sich der Beschwerdeführer weder durch die regelmässigen Verurteilungen und die dabei ausgesprochenen Sanktionen noch durch eine fremdenpolizeiliche Verwarnung im Jahr 2001 hat beeindrucken und von neuerlichen Gesetzesverstössen abhalten lassen. So musste er in den Jahren 2003 bis 2005 nicht weniger als achtmal wegen des gleichen Delikts (Benutzung eines öffentlichen Verkehrsmittels ohne gültigen Fahrausweis) zur Verantwortung gezogen werden. Selbst nach der Verurteilung durch das Kriminalgericht machte er sich wenig später der Veruntreuung schuldig. Ein derartiges Verhalten lässt den Beschwerdeführer als unbelehrbar und renitent erscheinen. Abgesehen davon, dass es ihm gelungen ist, erfolgreich eine Anlehre als Metallbearbeiter zu absolvieren, gab der Beschwerdeführer auch im Massnahmenvollzug zu Beschwerden Anlass, wo er (gemäss Aufhebungsentscheid vom 1. Oktober 2008) Mühe bekundete, allgemein gültige Verhaltensregeln einzuhalten, meist "aufbrausend, impulsiv, aggressiv bzw. bedrohlich" reagierte und damit oft in die alten Verhaltensmuster zurückfiel, ohne dass diesbezüglich Fortschritte hätten erzielt werden können. Dem Beschwerdeführer musste mangels einer positiven Prognose nicht nur die bedingte Entlassung verweigert werden, sondern die Arbeitserziehungsmassnahme insgesamt wegen Aussichtslosigkeit als gescheitert abgebrochen und durch eine Freiheitsstrafe ersetzt werden. Unter den gegebenen Umständen erscheint die Entfernung und Fernhaltung des Beschwerdeführers nicht nur wegen den begangenen Straftaten angezeigt, sondern auch mit Blick darauf, dass von ihm, nachdem eine Resozialisierung insbesondere in charakterlicher Hinsicht im Massnahmenvollzug - entgegen den Behauptungen in der Beschwerde - gerade nicht bzw. nicht im erwünschten Masse gelungen ist, nach wie vor eine gegenwärtige Gefahr für die öffentliche Ordnung ausgeht. Seine Ausweisung aus der Schweiz entspricht damit einem eminenten öffentlichen Interesse.
2.4 Die gegenläufigen privaten Interessen des Beschwerdeführers am Verbleib in der Schweiz fallen demgegenüber weniger schwer ins Gewicht. Gegen seine Ausweisung spricht, dass der Beschwerdeführer, welcher im Familiennachzug in die Schweiz kam, bereits seit seinem sechsten Altersjahr, d.h. nunmehr seit über 20 Jahren und damit den weitaus grössten Teil seines Lebens hier weilt. Sein Heimatland Mazedonien dürfte ihm nicht (mehr) aus eigener Erfahrung bekannt sein. Allerdings ist davon auszugehen, dass ihm Kultur und Gepflogenheiten durch sein Elternhaus vermittelt worden und somit nicht gänzlich unvertraut sind. Dass er sprachlich nicht in der Lage wäre, sich in Mazedonien zu verständigen, ist insofern wenig glaubwürdig. Daran ändert auch nichts, dass der Beschwerdeführer als Mazedonier der albanisch-sprachigen Minderheit, welche immerhin über einen Fünftel der Bevölkerung des Landes ausmacht, die Mehrheitssprache nicht spricht. Hinzu kommt dass seine Mutter und sein Bruder zwischenzeitlich nach Mazedonien zurückgekehrt sind, womit er dort über Bezugspersonen aus dem familiären Umfeld verfügt, mit denen er nach seiner Rückkehr wieder in Kontakt treten kann. Der kinderlose und ledige Beschwerdeführer lebt - wie er vor Bundesgericht erstmals vorbringt - angeblich inzwischen mit einer Freundin zusammen, welche er demnächst zu heiraten beabsichtige. Soweit als Novum überhaupt zulässig (oben E. 1.4), ist diesem Einwand entgegenzuhalten, dass die erwähnte Beziehung offensichtlich erst zu einem Zeitpunkt eingegangen wurde, als ein weiterer Aufenthalt des Beschwerdeführers in der Schweiz bereits ungewiss war. Auch wenn es tatsächlich zu diesem Eheschluss kommen sollte, vermöchten bei der gegebenen Sachlage die manifesten öffentlichen Interessen an einer Ausweisung des Beschwerdeführers (E. 2.3) einen diesbezüglichen Eingriff ins Recht auf Achtung des Familienlebens gemäss Art. 8 EMRK bzw. <ref-law> zu rechtfertigen. Nichts zu ändern vermag ferner der Umstand, dass es dem Beschwerdeführer nach anfänglichen Schwierigkeiten mit verschiedenen Arbeitgebern inzwischen gelungen ist, eine Anstellung als temporärer Reinigungsmitarbeiter zu finden und er von seinem Arbeitgeber geschätzt wird. Dank der abgeschlossenen Anlehre als Metallbearbeiter sollte es dem Beschwerdeführer möglich sein, auch in Mazedonien wieder Arbeit zu finden.
In Würdigung der genannten Umstände erweist sich die Ausweisung als verhältnismässig und der angefochtene Entscheid mithin als bundesrechts- und konventionskonform.
3. Nach dem Gesagten ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten als unbegründet abzuweisen.
Der Beschwerdeführer hat für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege und Verbeiständung ersucht. Aufgrund der dargestellten, schon im angefochtenen Urteil zutreffend wiedergegebenen Sach- und Rechtslage besass das vorliegende Rechtsmittel keine ernsthaften Erfolgsaussichten; das Gesuch ist demzufolge abzuweisen (<ref-law>).
Entsprechend dem Ausgang sind die Kosten des bundesgerichtlichen Verfahrens dem Beschwerdeführer aufzuerlegen (<ref-law>), wobei seiner finanziellen Lage bei der Bemessung der Gerichtsgebühr Rechnung zu tragen ist (vgl. <ref-law>). Auf die Zusprechung einer Parteientschädigung besteht kein Anspruch (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Migration und dem Verwaltungsgericht des Kantons Luzern sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 9. September 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Moser