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.