Sachverhalt:
A.
Nachdem A._ eine ihm mit Urteil des Obergerichts Appenzell Ausserrhoden vom 7. März 2017 auferlegte Geldstrafe nicht bezahlt hatte, wurde er vom Justizsekretariat des Kantons Appenzell Ausserrhoden mit Vollzugsbefehl vom 25. Mai 2018 zum Antritt der Ersatzfreiheitsstrafe am 3. Juli 2018 aufgeboten. Mit dem Hinweis, sich derzeit in Peru aufzuhalten, erhob A._ am 12. Juni 2018 gegen das Aufgebot zum Strafantritt Rekurs. Das Verfahren wurde in der Folge sistiert und vom Departement Inneres und Sicherheit des Kantons Appenzell Ausserrhoden (DIS) am 22. Dezember 2020 wieder aufgenommen. Mit der Wiederaufnahme wies das DIS den Rekurs von A._ ab und ordnete an, die Freiheitsstrafe von zehn Tagen sei innert einer Frist von 14 Tagen ab Rechtskraft der Verfügung um 9.00 Uhr in der Strafanstalt Gmünden anzutreten.
B.
Gegen diese Verfügung gelangte A._ am 30. Januar 2021 mit Beschwerde ans Obergericht des Kantons Appenzell Ausserrhoden. Am 5. Februar 2021 stellte er dem Obergericht zudem ein Gesuch um unentgeltliche Rechtspflege.
Das Obergericht wies das Gesuch von A._ um unentgeltliche Rechtspflege mit Verfügung vom 30. März 2021 ab. Am 28. Mai 2021 forderte es ihn auf, für die Kosten des Beschwerdeverfahrens einen Vorschuss von Fr. 800.-- zu leisten und drohte ihm an, dass nach ungenutztem Ablauf dieser Frist auf die Beschwerde nicht eingetreten werde. Mit Verfügung vom 21. Juni 2021 trat das Obergericht auf die Beschwerde nicht ein.
C.
C.a. A._ erhebt gegen die Verfügungen des Obergerichts vom 30. März, 28. Mai und 21. Juni 2021 Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, die Verfügungen seien vollumfänglich aufzuheben. Ihm sei für das kantonale Verfahren die unentgeltliche Rechtspflege zu gewähren. Eventualiter sei die Angelegenheit zur Neubeurteilung im Sinne der Begründung zurückzuweisen. Der Beschwerde sei die aufschiebende Wirkung zu gewähren. Zusätzlich ersucht er auch für das bundesgerichtliche Verfahren um Gewährung der unentgeltlichen Rechtspflege.
C.b. Die Akten des kantonalen Verfahrens wurden beigezogen.
C.c. Das DIS verzichtete auf eine Vernehmlassung und verwies stattdessen auf die Vorakten. Das Obergericht liess sich innert Frist nicht vernehmen.

Erwägungen:
1.
1.1. Gemäss Art. 100 Abs. 1 BGG ist die Beschwerde gegen einen Entscheid innert 30 Tagen nach der Eröffnung der vollständigen Ausfertigung beim Bundesgericht einzureichen. Bei der 30-tägigen Beschwerdefrist handelt es sich um eine gesetzliche Frist, die nicht erstreckt werden kann (Art. 47 Abs. 1 BGG).
Soweit sich die Beschwerde gegen die Verfügung der Vorinstanz vom 30. März 2021 richtet, mit der das Gesuch um unentgeltliche Rechtspflege abgewiesen wurde, ist sie verspätet.
1.2. Der Beschwerdeführer ersucht gestützt auf Art. 50 Abs. 1 BGG um Wiederherstellung der Frist. Er macht geltend, während die Verfügung vom 28. Mai 2021 einen Hinweis enthalten habe, dass bei nicht fristgerechter Bezahlung des Kostenvorschusses auf seine Beschwerde nicht eingetreten werde, habe ein solcher Hinweis in der Verfügung vom 30. März 2021 gefehlt. Er sei damals in Unkenntnis darüber gelassen worden, dass beabsichtigt werde, nach Nichtbezahlung des Kostenvorschusses auf die Beschwerde nicht einzutreten. An der Beantwortung der Frage, ob die Vorinstanz mit diesem Vorgehen gegen die Bundesverfassung verstossen habe, bestehe ein öffentliches Interesse. Das Vorgehen könne zudem bewirken, dass das aktuelle praktische Interesse an der Gewährung der unentgeltlichen Rechtspflege wegfalle, bevor das Bundesgericht über den fehlenden Hinweis auf ein allfälliges Nichteintreten in der Verfügung vom 30. März 2021 befinden könne. Die Verweigerung der unenteltlichen Rechtspflege lasse sich so kaum je rechtzeitig überprüfen, weshalb auf das Erfordernis des aktuellen praktischen Interesses zu verzichten sei.
1.3. Gemäss Art. 50 Abs. 1 BGG wird die Frist wiederhergestellt, wenn eine Partei oder ihr Vertreter durch einen anderen Grund als die mangelhafte Eröffnung unverschuldeterweise abgehalten worden ist, fristgerecht zu handeln, sofern die Partei unter Angabe des Grundes innert 30 Tagen nach Wegfall des Hindernisses darum ersucht und die versäumte Rechtshandlung nachholt. Ein unverschuldetes Hindernis im Sinne dieser Bestimmung kann nur angenommen werden, wenn der betroffenen Partei keinerlei Verschulden trifft (vgl. <ref-ruling> E. 1.3; Urteil 6B_1329/2020 vom 20. Mai 2021 E. 1.3.3 mit Hinweis). Nach der Rechtsprechung kann die Wiederherstellung nur bei klarer Schuldlosigkeit gewährt werden. Jedes Verschulden einer Partei, ihres Vertreters oder beigezogener Hilfspersonen, so geringfügig es sein mag, schliesst die Wiederherstellung aus. Es gilt ein strenger Massstab (vgl. Urteile 6B_1367/2020 vom 9. Februar 2021 E. 3; 6B_318/2012 vom 21. Januar 2013 E. 1.2; je mit Hinweisen). Die blosse Unkenntnis von Rechtsregeln (insbesondere verfahrensrechtlicher Natur) bzw. ein Irrtum über deren Tragweite kann vorbehältlich besonderer Umstände keinen Anlass zur Fristwiederherstellung geben (vgl. Urteile 5A_969/2018 vom 6. Mai 2019 E. 2.2.3; 8C_953/2009 und 8C_1039/2009 vom 23. Februar 2010 E. 6.4.2; je mit Hinweisen; Urteil 1B_208/2010 vom 19. August 2010).
1.4. Vorliegend kann nicht gesagt werden, dass den Beschwerdeführer keinerlei Verschulden an der Fristversäumnis trifft. Nachdem sein Gesuch um unentgeltliche Rechtspflege abgewiesen worden war, stand fest, dass der Beschwerdeführer allenfalls für die Kosten des kantonalen Beschwerdeverfahrens haftbar gemacht werden könnte (vgl. Art. 19 Abs. 1 des Gesetzes des Kantons Appenzell Ausserrhoden vom 9. September 2002 über die Verwaltungsrechtspflege [VRPG; bGS 143.1]). Es musste ihm folglich bereits damals klar gewesen sein, dass ihm gewisse Nachteile drohen könnten, sollte die fragliche Verfügung in Rechtskraft erwachsen, zumal darin ausdrücklich auf solche Nachteile hingewiesen wurde (vgl. auch die konstante Rechtsprechung in den Urteilen 6B_15/2019 vom 15. Mai 2019 E. 2.1 [Strafverfahren]; 2C_621/2019 vom 13. Januar 2020 E. 2.3 [Verwaltungsverfahren]; 4A_375/2020 vom 23. September 2020 E. 1.2 [Zivilverfahren]; je mit Hinweisen). Diese war zudem mit einer Rechtsmittelbelehrung versehen. Weiter stützt sich das Vorgehen der Vorinstanz auf eine gesetzliche Grundlage: Gemäss Art. 21 VRPG/AR kann von der rekurs- oder beschwerdeführenden Partei ein Kostenvorschuss verlangt werden. Es ist ihr eine angemessene Frist anzusetzen und ihr anzudrohen, dass im Säumnisfall auf das Rechtsmittel nicht eingetreten werde. Der Beschwerdeführer musste somit damit rechnen, dass von ihm ein Kostenvorschuss einverlangt wird und dass auf seine Beschwerde im Falle von dessen Nichtbezahlung nicht eingetreten wird, auch wenn dies in der Verfügung vom 30. März 2021 nicht erwähnt wurde. Eine allfällige Unkenntnis der genannten Bestimmung ändert nach der Rechtsprechung nichts daran, dass er das Fristversäumnis selbst zu verantworten hat. Seiner Beschwerde sind keine besonderen Umstände zu entnehmen, die einen anderen Schluss nahelegen würden. Nach dem Gesagten fällt eine Wiederherstellung der Beschwerdefrist nach Art. 100 Abs. 1 BGG ausser Betracht und wird auf die Beschwerde, soweit sie sich gegen die Verfügung vom 30. März 2021 richtet, wegen Verspätung nicht eingetreten.
2.
2.1. Gemäss Art. 42 Abs. 1 BGG hat die Beschwerde ein Rechtsbegehren zu enthalten. Da die Beschwerde an das Bundesgericht grundsätzlich ein reformatorisches Rechtsmittel ist (Art. 107 Abs. 2 BGG), muss es sich dabei um einen Antrag in der Sache handeln. Allerdings reicht ein Begehren ohne einen solchen Antrag aus, wenn sich aus der Beschwerdebegründung, die zur Interpretation des Rechtsbegehrens beigezogen werden kann, zweifelsfrei ergibt, was mit der Beschwerde angestrebt wird (<ref-ruling> E. 1.3; Urteil 6B_42/2021 vom 8. Juli 2021 E. 2.1; je mit Hinweisen). In der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (Art. 42 Abs. 2 BGG).
2.2. Betreffend die Verfügungen vom 28. Mai und 21. Juni 2021 stellt der Beschwerdeführer keinen Antrag in der Sache. Seinen Antrag auf Aufhebung der genannten Verfügungen begründet er zudem nicht konkret, weshalb darauf grundsätzlich nicht einzutreten ist.
Selbst wenn dieses Begehren als Antrag auf Anweisung an die Vorinstanz, seine Beschwerde materiell zu behandeln, interpretiert und davon ausgegangen würde, mit seinen Ausführungen zur Verfügung vom 30. März 2021 sei auch die Beschwerde hinsichtlich der Verfügungen vom 28. Mai und 21. Juni 2021 hinreichend begründet, wäre dieser kein Erfolg beschieden: Wie bereits ausgeführt, beruht die Einholung eines Kostenvorschusses mit gleichzeitiger Androhung, dass im Säumnisfall auf die Beschwerde nicht eingetreten werde, auf einer gesetzlichen Grundlage (Art. 21 VRPG/AR). Als kantonale Bestimmung überprüft das Bundesgericht diese grundsätzlich nur auf Willkür (Art. 95 BGG; <ref-ruling> E. 1.2 mit Hinweisen). Dass diese Bestimmung willkürlich angewendet worden wäre, wird in der Beschwerde nicht vorgebracht und ist auch in keiner Weise ersichtlich. Damit erweist sich die Beschwerde gegen die Verfügung vom 28. Mai 2021 als unbegründet. Der Beschwerdeführer bestreitet im Weiteren nicht, den einverlangten Gerichtskostenvorschuss nicht (fristgerecht) geleistet zu haben. Folglich ist die Vorinstanz gestützt auf Art. 21 VRPG/AR zu Recht nicht auf seine Beschwerde eingetreten. Problematisch ist einzig, dass sie am 21. Juni 2021 das Nichteintreten verfügt hat, bevor die Verfügung vom 28. Mai 2021 in Rechtskraft erwachsen ist. Im Grunde genommen hat sie dem Beschwerdeführer damit den ordentlichen Rechtsweg abgeschnitten. Da das Vorgehen der Vorinstanz davon abgesehen jedoch als korrekt zu beurteilen ist und dem Beschwerdeführer bei den Kostenfolgen keine Nachteile erwachsen (sind), scheint es in dieser besonderen Konstellation nicht angezeigt, die Sache einzig zur erneuten Verfügung, dass wegen Nichtbezahlung des Gerichtskostenvorschusses auf die Beschwerde nicht eingetreten werde, an die Vorinstanz zurückzuweisen.
3.
Die Beschwerde wird abgewiesen, soweit überhaupt darauf eingetreten werden kann. Demnach wird der Beschwerdeführer für das bundesgerichtliche Verfahren kostenpflichtig (Art. 66 Abs. 1 BGG). Sein Gesuch um unentgeltliche Rechtspflege wird wegen Aussichtslosigkeit abgewiesen (Art. 64 Abs. 1 BGG). Seinen finanziellen Verhältnissen wird mit reduzierten Gerichtskosten Rechnung getragen (Art. 65 Abs. 2 BGG). Mit dem Entscheid in der Sache wird der Antrag um aufschiebende Wirkung gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Das Gesuch um Wiederherstellung der Beschwerdefrist wird abgewiesen.
2.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
3.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
4.
Die Gerichtskosten von Fr. 1'200.-- werden dem Beschwerdeführer auferlegt.
5.
Dieses Urteil wird den Parteien und dem Obergericht Appenzell Ausserrhoden, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 3. November 2021
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Jacquemoud-Rossari
Die Gerichtsschreiberin: Lustenberger