Sachverhalt:
A. X._ wurde mit Entscheid des Strafgerichts Basel-Stadt vom 19. März 2009 wegen mehreren Delikten (insbesondere wegen qualifizierten Raubes, einfacher Körperverletzung, mehrfacher Gefährdung des Lebens, gewerbsmässigen Diebstahls und qualifizierter Sachbeschädigung) zu einer Freiheitsstrafe von 9 Jahren verurteilt.
Am 23. April 2009 wurde er in die Sicherheitsabteilung der Strafanstalt Bostadel eingewiesen. Ein am 14. Juli 2009 gestelltes Gesuch um Versetzung in den Normalvollzug wies das kantonale Amt für Justizvollzug mit Entscheid vom 24. Juli 2009 ab. Dagegen erhob X._ am 27. Juli 2009 Rekurs an das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt.
Am 6. Oktober 2009, noch während des laufenden Rekursverfahrens, ersuchte X._ erneut um Platzierung in den Normalvollzug. Das Amt für Justizvollzug kam diesem Gesuch am 22. Oktober 2009 nach. Das beim Justiz- und Sicherheitsdepartement hängige Rekursverfahren wurde am 17. November 2009 als gegenstandslos abgeschrieben.
B. Rechtsanwalt Stefan Suter beantragte am 18. November 2009 beim Justiz- und Sicherheitsdepartement die Übernahme der Kosten für die Verbeiständung von X._ im Verfahren betreffend seine Versetzung. Dieses lehnte das Gesuch mit Entscheid vom 9. Dezember 2009 ab. Den von X._ dagegen erhobenen Rekurs wies das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht am 10. Mai 2010 ab.
C. X._ gelangt mit Beschwerde ans Bundesgericht. Er beantragt im Wesentlichen die Aufhebung des angefochtenen Entscheids des Appellationsgerichts. Des Weiteren ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
D. Das Appellationsgericht des Kantons Basel-Stadt und das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt beantragen in ihren Vernehmlassungen, die Beschwerde sei abzuweisen.

Erwägungen:
1. 1.1 Der Beschwerdeführer rügt <ref-law> als verletzt. Er sei in die Sicherheitsabteilung der Strafanstalt Bostadel eingewiesen worden, obwohl keine besondere Fluchtgefahr bestanden habe. Der von ihm erhobene Rekurs vom 27. Juli 2009 an das Justiz- und Sicherheitsdepartement sei nicht von vornherein aussichtslos gewesen. Jede über die nötigen finanziellen Mittel verfügende Person hätte in der nämlichen Situation ein Gesuch um Versetzung in den Normalvollzug gestellt respektive ein Rechtsmittel eingelegt (Beschwerde S. 2 f.).
1.2 Die Vorinstanz erwägt, im Zeitpunkt des ersten Gesuchs am 14. Juli 2009 seien alle beteiligten Behörden von einer sehr grossen Fluchtgefahr und dem Risiko einer gewaltsamen Befreiungsaktion mit einer Geiselnahme ausgegangen. Ein vermögender Verurteilter in der Lage des Beschwerdeführers hätte kein Gesuch um Versetzung in den Normalvollzug gestellt und bei dessen Abweisung keinen Rekurs erhoben. Vielmehr hätte er die stufenweise Lockerung des Strafvollzugs abgewartet. Deshalb seien das Gesuch vom 14. Juli 2009 und der Rekurs vom 27. Juli 2009 zu Recht als von vornherein aussichtslos beurteilt worden (angefochtener Entscheid S. 5 ff.).
1.3 Jede Person, die nicht über die erforderlichen Mittel verfügt, hat Anspruch auf unentgeltliche Rechtspflege, wenn ihr Rechtsbegehren nicht aussichtslos erscheint. Soweit es zur Wahrung ihrer Rechte notwendig ist, hat sie ausserdem Anspruch auf unentgeltlichen Rechtsbeistand (<ref-law>).
Parteistandpunkte sind als aussichtslos anzusehen, wenn die Aussichten des prozessualen Obsiegens beträchtlich geringer sind als die des Unterliegens. Wenn sich Gewinn- und Verlustchancen ungefähr die Waage halten oder wenn das Obsiegen nur wenig unwahrscheinlicher erscheint, liegt keine Aussichtslosigkeit vor. Massgeblich ist, ob eine Partei, die über die nötigen finanziellen Mittel verfügt, sich bei vernünftiger Überlegung zum Prozess entschliessen würde. Ein Rechtsuchender soll einen Prozess, den er auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er ihn nichts kostet. Ob im Einzelfall genügende Erfolgsaussichten bestehen, beurteilt sich nach den Verhältnissen zur Zeit, in der das Gesuch um unentgeltliche Rechtspflege gestellt wurde (<ref-ruling> E. 5 S. 616 mit Hinweisen).
Ob eine unentgeltliche Rechtsverbeiständung sachlich notwendig ist, hängt von den konkreten Umständen des Einzelfalles ab. Die Rechtsnatur des Verfahrens ist ohne Belang. Grundsätzlich fällt die unentgeltliche Verbeiständung für jedes staatliche Verfahren in Betracht, in das der Gesuchsteller einbezogen wird oder das zur Wahrung seiner Rechte notwendig ist. Die bedürftige Partei hat Anspruch auf unentgeltliche Verbeiständung, wenn ihre Interessen in schwerwiegender Weise betroffen sind und der Fall in tatsächlicher oder rechtlicher Hinsicht Schwierigkeiten bietet, die den Beizug eines Rechtsvertreters erforderlich machen. Droht das in Frage stehende Verfahren besonders stark in die Rechtsposition der betroffenen Person einzugreifen, ist die Bestellung eines unentgeltlichen Rechtsvertreters grundsätzlich geboten, sonst nur, wenn zur relativen Schwere des Falles besondere tatsächliche oder rechtliche Schwierigkeiten hinzukommen, denen der Gesuchsteller auf sich alleine gestellt nicht gewachsen wäre (<ref-ruling> E. 2.2 S. 182 mit Hinweisen).
1.4 Die Vorinstanz schätzt das Gesuch des mittellosen Beschwerdeführers um Versetzung in den Normalvollzug und das Rechtsmittel gegen den abweisenden Entscheid des Amtes für Justizvollzug als von vornherein aussichtslos ein. Mit der Frage der Notwendigkeit einer Verbeiständung befasst sie sich in der Folge nicht.
1.4.1 Zu prüfen ist in einem ersten Schritt, ob das Gesuch vom 14. Juli 2009 als aussichtslos bezeichnet werden muss. Der Beschwerdeführer befand sich in jenem Zeitpunkt seit rund drei Monaten in der Sicherheitsabteilung der interkantonalen Strafanstalt Bostadel. Ob und gegebenenfalls in welchem Umfang er damals über den geplanten und bisherigen Vollzugsverlauf sowie über mögliche Vollzugslockerungen aufgeklärt worden war, lässt sich den vorinstanzlichen Akten nicht entnehmen. Ebenso wenig ist belegt, dass der Beschwerdeführer über den Grund seiner Versetzung in die Sicherheitsabteilung und die voraussichtliche Dauer informiert wurde. Gegenteiliges geht aus dem abweisenden Entscheid des Amtes für Justizvollzug vom 24. Juli 2009 nicht hervor und stellt die Vorinstanz nicht fest. Mangels entsprechender Anhaltspunkte ist demnach davon auszugehen, dass dem Beschwerdeführer die Gründe und den möglichen weiteren Verlauf seines Aufenthalts nicht eröffnet wurden. Dies geht (zumindest implizit) auch aus einem Schreiben seines Rechtsbeistandes vom 24. Juni 2009 an die Strafanstalt hervor, worin sich dieser nach dem Grund der "speziellen Vollzugsform" erkundigt. Deshalb ist die Argumentation der Vorinstanz, ein vermögender Verurteilter hätte bei vernünftiger Überlegung kein Gesuch um Versetzung gestellt, sondern lediglich zugewartet, mit Blick auf die fehlende Aufklärung unhaltbar.
1.4.2 Ist das Versetzungsgesuch nicht als von vornherein aussichtslos einzustufen, so besteht ein Anspruch auf unentgeltliche Verbeiständung, soweit sie notwendig ist. Die Notwendigkeit beurteilt sich nach der Gesamtheit der konkreten Umstände. In welcher Vollzugsstufe sich der Beschwerdeführer im Juli 2009 befand, geht aus dem angefochtenen Entscheid und den Akten nicht hervor. Mithin ist unklar, welche Aktivitäten ihm offenstanden, respektive welche Einschränkungen er im Vergleich zum gewöhnlichen Vollzug zu erdulden hatte (vgl. vorinstanzliche Akten, dreistufiger Vollzugsverlauf gemäss "Definition & Vollzugsauftrag Sicherheitsabteilung"). Dies kann jedoch dahingestellt bleiben. Es geht (auch unter Berücksichtigung der Länge des Verbleibs auf der Sicherheitsabteilung) nicht um einen für den Beschwerdeführer besonders schwerwiegenden Eingriff. Ebenso wenig ist die Dauer des Aufenthalts auf der Sicherheitsabteilung für den späteren Normalvollzug von erheblicher Bedeutung. Deshalb müssen besondere tatsächliche oder rechtliche Schwierigkeiten hinzukommen, welche eine Verbeiständung rechtfertigen. Solche Schwierigkeiten macht der Beschwerdeführer nicht geltend. Er war denn auch durchaus fähig, ein entsprechendes, kurzgefasstes Gesuch (im Oktober 2009) in eigenem Namen einzureichen. Das entsprechende Verfahren ist weder kompliziert ausgestaltet, noch wirft es komplexe Fragen auf. Mithin war es dem Beschwerdeführer möglich, auf sich alleine gestellt sein Anliegen sachgerecht, hinreichend und mit Erfolg zu vertreten. Gleiches wäre ihm auch im Rahmen seiner ersten Eingabe möglich gewesen. Dass die Vorinstanz die unentgeltliche Vertretung betreffend das Gesuch um Versetzung verweigert, ist, im Ergebnis, verfassungsrechtlich nicht zu beanstanden.
1.4.3
1.4.3.1 Zu prüfen ist in einem zweiten Schritt, wie es sich mit dem Rekursverfahren an das Justiz- und Sicherheitsdepartement (nachfolgend: JSD) verhält. Bei den Gewinnaussichten und Verlustgefahren eines Rechtsmittels darf der unterinstanzliche Entscheid in die Prüfung miteinbezogen werden (Gerold Steinmann, in: Die schweizerische Bundesverfassung, St. Galler Kommentar, 2. Aufl. 2008, N. 39 zu <ref-law>). Das Amt für Justizvollzug erwog in seinem abweisenden Entscheid vom 24. Juli 2009, im Zeitpunkt der Verurteilung habe ein erheblich erhöhtes Fluchtrisiko bestanden. Es hätten Anhaltspunkte dafür vorgelegen, dass Dritte den Beschwerdeführer gewaltsam befreien würden. Deshalb habe die erstinstanzliche Hauptverhandlung nicht in den Räumlichkeiten des Strafgerichts, sondern in jenen der Staatsanwaltschaft stattgefunden. In Italien werde gegen den Beschwerdeführer wegen eines Tötungsdelikts ermittelt, weshalb er allenfalls im Ausland eine weitere Inhaftierung zu gewärtigen habe. Das Risiko, dass er sich dem Vollzug der Freiheitsstrafe mittels Flucht entziehen würde, sei erheblich. Eine Verlegung in den Normalvollzug der Strafanstalt wäre nach knapp drei Monaten Aufenthalt in der Sicherheitsabteilung nicht zu verantworten und klar verfrüht. Die Notwendigkeit dieses Verbleibs werde periodisch überprüft, spätestens nach einer Dauer von sechs Monaten.
Die Vorinstanz stellt gestützt darauf ebenfalls ein erhöhtes Fluchtrisiko fest. Sie verweist zudem auf das Urteil des Strafgerichts vom 19. März 2009, wonach unter anderem der Beschwerdeführer mehrere Gewaltdelikte als Vorstrafen aufweise und von Serbien sowie Italien wegen eines Tötungsdeliktes respektive eines Versuchs dazu ausgeschrieben sei. Er gehöre zudem zum Umfeld eines gewissen Y._, welcher von Mittätern gewaltsam aus der Untersuchungshaft befreit worden sei. Auch sei er gemäss eigenen Angaben bereits einmal aus einer Strafanstalt geflüchtet. Schliesslich liege, so die Vorinstanz, ein Rapport des Untersuchungsgefängnisses Basel-Stadt vor, wonach ein Mithäftling glaubhaft über eine unter anderem vom Beschwerdeführer - in früheren Jahren - geplante Geiselnahme berichtet habe.
1.4.3.2 Der Beschwerdeführer beschränkt sich, wie auch in der Rekursschrift ans JSD, im Wesentlichen darauf, die ihm zugesprochene massive Fluchtgefahr in Abrede zu stellen. Mit den verbindlichen Feststellungen der Vorinstanz (<ref-law>) setzt er sich nicht auseinander, und er zeigt nicht auf, inwiefern diese willkürlich sein sollten (vgl. zum Begriff der Willkür <ref-ruling> E. 1.3 S. 4 f. mit Hinweisen). Zudem befand er sich entgegen seiner Darstellung nicht "völlig abgeschottet in Isolationshaft". Soweit er zum Letzteren beispielsweise behauptet, das Amt für Justizvollzug habe in seinem Entscheid vom 24. Juli 2009 bestätigt, dass er keiner Arbeit habe nachgehen können, verkennt er, dass in der genannten Verfügung das Gegenteil festgehalten wird. Auf die Beschwerde ist in diesem Punkt nicht einzutreten (<ref-law>).
Selbst wenn auf die Rüge eingetreten werden könnte, wäre sie aus nachstehenden Gründen unbegründet: Mit Blick auf die Erwägungen des Entscheids des Amtes für Justizvollzug vom 24. Juli 2009, die im Urteil des Strafgerichts Basel-Stadt vom 19. März 2009 dargelegten Hinweise für eine Flucht (unter anderem die bereits geglückte Flucht aus einer Strafanstalt und eine mögliche Verbindung zu Y._) sowie die von der Vorinstanz aufgezeigten Umstände (insbesondere eine vom Beschwerdeführer geplante Geiselnahme) ist die Rekurseingabe an das JSD als von vornherein aussichtslos einzuschätzen. Mithin kann in einer summarischen Prüfung der Erfolgsaussichten als unwahrscheinlich bezeichnet werden, dass das JSD, hätte es das Verfahren nicht als gegenstandslos abgeschrieben, nach einem knapp dreimonatigen Aufenthalt des Beschwerdeführers in der Sicherheitsabteilung zu einer positiven Einschätzung gelangt wäre. Die damaligen Prozesschancen können demnach nicht als intakt beurteilt werden. Vielmehr erschien bei dieser Sachlage das Verfahren im massgeblichen Zeitpunkt der Einreichung des Rekurses als von vornherein aussichtslos. Die Vorinstanz weist das Armenrechtsgesuch des Beschwerdeführers folglich zu Recht ab, und eine Verletzung von <ref-law> liegt nicht vor. Entgegen dem Dafürhalten des Beschwerdeführers ist es schliesslich nicht widersprüchlich, wenn die Vorinstanz die unentgeltliche Verbeiständung verweigert und gleichzeitig von der Erhebung von Kosten absieht. Die Beschwerde erweist sich daher als unbegründet, soweit sie den Begründungsanforderungen von Art. 42 Abs. 2 und <ref-law> überhaupt zu genügen vermag.
2. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist abzuweisen, da die Beschwerde von vornherein aussichtslos war (<ref-law> e contrario).
Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Seinen angespannten finanziellen Verhältnissen ist mit reduzierten Gerichtskosten Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht schriftlich mitgeteilt.
Lausanne, 6. Dezember 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Faga