Erwägungen:
1. 1.1 Der mazedonische Staatsangehörige X._ (geb. 1976) reiste im Juli 1991 im Alter von fünfzehn Jahren im Familiennachzug in die Schweiz ein. Fünf Jahre später erhielt er die Niederlassungsbewilligung. Wegen strafrechtlicher Verurteilungen, Schuldenmacherei und Fürsorgeabhängigkeit wies die Fremdenpolizei des Kantons Basel-Stadt X._ am 29. September 2004 für unbestimmte Zeit aus der Schweiz aus. Diesen Entscheid bestätigte das kantonale Sicherheitsdepartement am 10. März 2005. In seinem dagegen gerichteten Rekurs machte X._ erstmals geltend, er leide an einer schweren Erbkrankheit, die bei ihm erst im Dezember 2004 diagnostiziert worden und für welche die medizinische Betreuung in seinem Heimatland nicht gesichert sei. Das Appellationsgericht des Kantons Basel-Stadt hiess am 13. Dezember 2005 den Rekurs teilweise gut und wies die Sache an das Sicherheitsdepartement zurück zur weiteren Abklärung der Frage, ob X._ eine Rückkehr nach Mazedonien aus medizinischer Sicht zumutbar sei. Am 11. September 2008 bestätigte das Sicherheitsdepartement erneut die Ausweisungsverfügung. Den dagegen erhobenen Rekurs wies das Appellationsgericht am 12. Januar 2009 ab.
1.2 Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 16. Februar 2009 beantragt X._ dem Bundesgericht, das Urteil des Appellationsgerichts vom 12. Januar 2009 aufzuheben und die kantonalen Instanzen anzuweisen, ihm die Niederlassungsbewilligung zu "verlängern".
1.3 Das kantonale Sicherheitsdepartement (heute: Justiz- und Sicherheitsdepartement), das Appellationsgericht sowie das Bundesamt für Migration stellen den Antrag, die Beschwerde abzuweisen.
1.4 Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde mit Verfügung vom 19. Februar 2009 antragsgemäss die aufschiebende Wirkung zuerkannt. Ein Gesuch des Sicherheitsdepartements um Entzug der aufschiebenden Wirkung hat er am 13. Mai 2009 abgewiesen.
2. Die Vorinstanzen gehen davon aus, dass die Ausweisungsgründe der Art. 10 Abs. 1 lit. a, b und d des hier noch anwendbaren Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121, in der Fassung vom 8. Oktober 1948, AS 1949 I 221 und 227) vorliegen (vgl. zum Übergangsrecht: Art. 126 Abs. 1 AuG; Urteil 2C_745/2008 vom 24. Februar 2009 E. 1.2). Der Beschwerdeführer bestreitet dies zu Recht nicht. Unter anderem räumt er ein, dass er mehrfach strafrechtlich verurteilt worden ist, insbesondere am 6. Dezember 2001 zu einer Gefängnisstrafe von zweieinhalb Jahren wegen Raub, versuchter Erpressung, gewerbsmässigem Diebstahl und Betrug, und am 19. Dezember 2007 zu einer Freiheitsstrafe von fünf Jahren - unter Einbezug der Reststrafe von zehn Monaten und fünfzehn Tagen aus der Verurteilung vom 6. Dezember 2001 - vor allem wegen mehrfachem gewerbs- und bandenmässigem Diebstahl.
3. 3.1 Der Beschwerdeführer macht vor Bundesgericht lediglich geltend, er leide an einer unheilbaren Krankheit (Hämochromatose bzw. Eisenspeicherkrankheit), die ohne Behandlung ein Organversagen mit Todeseintritt zur Folge habe. Die Universitätsklinik Skopje habe bestätigt, dass die Behandlungsmöglichkeiten in Mazedonien sehr beschränkt seien. Daher verletze seine Ausweisung sein Recht auf Leben und Menschenwürde und verstosse auch gegen Art. 3 EMRK.
3.2 Die Vorinstanz geht zutreffend davon aus, dass bei der nach Art. 11 Abs. 3 ANAG vorzunehmenden Interessenabwägung auch zu berücksichtigen ist, ob und inwieweit dem Ausländer aufgrund seines Gesundheitszustandes eine Rückkehr in seine Heimat zumutbar ist (vgl. <ref-ruling> E. 3.2 und 4.2 S. 116 ff.). Dabei spielt namentlich eine Rolle, ob dort Behandlungsmöglichkeiten bestehen. Soweit die medizinische Versorgung im Heimatland gewährleistet ist, kann sich der Ausländer regelmässig nicht darauf berufen, dass die Versorgung in der Schweiz einem höheren Standard entspricht (vgl. <ref-ruling> E. 5.3 S. 209 und Urteil 2C_826/2008 vom 6. März 2009 E. 3.5.3).
3.3 Gestützt auf Abklärungen bei verschiedenen Stellen hält das Appellationsgericht fest, die Behandlung der Hämochromatose durch regelmässige Aderlässe (Phlebotomien) und die Einnahme von Medikamenten sei in Mazedonien ebenso möglich wie in der Schweiz. Soweit die Medikamente in Mazedonien nicht vorrätig seien, könnten diese aus dem Ausland bezogen werden. Hiergegen wendet der Beschwerdeführer nur ein, die Medikamentenbeschaffung sei in seiner Heimat erschwert: das Organversagen trete aufgrund einer zu hohen Eisenbelastung unvorhergesehen ein, weshalb die Medikamente schnell verfügbar sein müssten und im Ernstfall nicht rechtzeitig aus dem Ausland beschafft werden könnten.
Der Beschwerdeführer übersieht indes, dass die überhöhte Eisenbelastung, welche sich letal auswirken kann, durch die in seiner Heimat - unstreitig - im gleichen Masse möglichen, regelmässigen Aderlässe verhindert werden kann. Nichts anderes gilt für die Verabreichung von spezifischen Wachstumsfaktoren zur Blutbildung, die das Universitätsspital Basel vorgesehen hatte. Nach den für das Bundesgericht verbindlichen Feststellungen der Vorinstanz geht es somit nicht um Massnahmen, die wegen unerwarteter Ereignisse zu treffen sind. Weder legt der Beschwerdeführer substantiiert dar noch ist ersichtlich, dass die diesbezüglichen Feststellungen der Vorinstanz offensichtlich falsch sind (vgl. Art. 97 und 105 BGG; <ref-ruling> E. 2.2 S. 41; <ref-ruling> E. 1.5 S. 68).
Der Beschwerdeführer macht darüber hinaus geltend, die Früherkennung sei "alles entscheidend", doch in seiner Heimat nicht möglich. Zwar trifft es nach den übereinstimmenden Ausführungen der Beteiligten zu, dass die Früherkennung, wie sie am Universitätsspital Basel stattfinden könnte, in Mazedonien derzeit nicht in gleicher Weise zur Verfügung steht. Das Universitätsspital hat allerdings auf eine alternative Behandlung hingewiesen, die auch in Mazedonien möglich ist (Bericht vom 14. August 2007). Dem Spital zufolge ist diese nur dann weniger wirksam, wenn die Überwachung nicht vollständig bleibt. Ausserdem weist die Vorinstanz darauf hin, dass der Beschwerdeführer die ihm Anfang 2005 nahegelegte Behandlung zur Früherkennung selber abgebrochen bzw. gar nicht angetreten hatte. Damit setzt sich der Beschwerdeführer nicht auseinander. Er wendet bloss ein, er sei ab Juli 2005 in Haft gewesen; es sei daher willkürlich, ihm vorzuwerfen, er habe keinerlei Bemühungen aufgenommen, um vom Gefängnis aus die vorgeschlagene Behandlung durchzuführen. Dieses Vorbringen ist unbehelflich, zumal der Beschwerdeführer - trotz entsprechenden Vorhalten durch die Vorinstanzen - nicht einmal behauptet, er habe im Gefängnis um Durchführung der vom Spital angebotenen, aufwendigeren Behandlung nachgesucht. Fehl geht sein Vorbringen, es wäre am Gefängnisarzt gewesen, ihn an eine Universitätsklinik zu weisen. Das Gleiche gilt für seinen Einwand, es sei ihm nicht zuzumuten, sein Verhalten mit Blick auf ein späteres ausländerrechtliches Verfahren auszurichten. Im Übrigen lief dieses Verfahren damals bereits. Auch hatte ihn weder der Ausbruch der Erbkrankheit noch eine laufende Bewährungszeit noch hängige Strafverfahren davon abgehalten, erneut und wiederholt deliktisch tätig zu werden.
4. Die Vorinstanz hat die privaten Interessen am Verbleib des Beschwerdeführers in der Schweiz - unter Einbeziehung der erwähnten Krankheit - mit denjenigen an seiner Fernhaltung in nicht zu beanstandender Weise gegeneinander abgewogen. Ihr Entscheid, die verfügte Ausweisung zu schützen, erweist sich als bundesrechts- und konventionskonform. Ergänzend wird auf die Ausführungen in ihren Urteilen vom 13. Dezember 2005 und 12. Januar 2009 verwiesen. Die Beschwerde ist offensichtlich unbegründet und kann daher im vereinfachten Verfahren mit summarischer Begründung erledigt werden (vgl. Art. 109 BGG).
5. Nach dem Dargelegten ist wegen Aussichtslosigkeit des Rechtsbegehrens auch der Antrag des Beschwerdeführers auf unentgeltliche Rechtspflege und Verbeiständung abzuweisen (Art. 64 Abs. 1 BGG). Bei diesem Ausgang hätte der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65 f. BGG). Mit Blick auf seine Einkommens- und Vermögensverhältnisse wird jedoch auf die Erhebung von Gerichtskosten verzichtet.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Es werden keine Gerichtskosten erhoben.
4. Dieses Urteil wird dem Beschwerdeführer, dem Justiz- und Sicherheitsdepartement sowie dem Appellationsgericht, als Verwaltungsgericht, des Kantons Basel-Stadt und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 30. Juni 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Merz