Sachverhalt: A. A.a. Der türkische Staatsangehörige B.A._ (geb. 1966) reiste am 9. November 1983 in die Schweiz ein und verfügt seit dem 15. August 1994 über eine Niederlassungsbewilligung. Im Jahr 1995 heiratete er seine Landsfrau A.A._ (geb. 1973), welche am 12. November 1990 in die Schweiz eingereist war und am 29. August 1995 eine Aufenthaltsbewilligung erhielt. Das Ehepaar hat zwei gemeinsame, volljährige Kinder. A.b. Ab dem Jahr 2000 verwarnten die Einwohnerdienste des Polizei- und Militärdepartements bzw. das Migrationsamt des Kantons Basel-Stadt (Migrationsamt) die Eheleute A._ mehrmals wegen stetig steigender Schulden, Betreibungen und Verlustscheinen. Per Juli 2000 waren im Betreibungs- und Verlustscheinregister Ausstände im Umfang von Fr. 34'755.05 zu Lasten der Eheleute A._ verzeichnet. Im Jahr 2004 (und danach wiederholt) wurde A.A._ deshalb die Erteilung der Niederlassungsbewilligung verweigert. Im Mai 2004 beliefen sich die Schulden bereits auf Fr. 120'476.20. Im Jahr 2005 wurde den Eheleuten A._ nach erneuter Verwarnung die Wegweisung aus der Schweiz angedroht, sollten sie weitere Schulden anhäufen. Per August 2010 beliefen sich deren Schulden auf Fr. 263'292.10. Auch eine mit den Eheleuten A._ im Juli 2012 geschlossene Integrationsvereinbarung und Verpflichtung, eine Schuldenberatung aufzusuchen, konnte das weitere Anwachsen der Schulden nicht verhindern. Im März 2018 waren zulasten von B.A._ 109 Verlustscheine im Umfang von Fr. 329'253.70 und zulasten A.A._ 82 Verlustscheine im Umfang von Fr. 193'446.70 registriert. A.c. Mit Strafbefehl des Bezirksstatthalteramts Arlesheim vom 11. Oktober 2010 wurde B.A._ wegen Fahrens in fahrunfähigem Zustand zu einer bedingten Geldstrafe von 25 Tagessätzen à Fr. 20.-- und zu einer Busse von Fr. 500.-- verurteilt. Eine weitere Verurteilung wegen desselben Tatbestandes erfolgte mit Strafbefehl der Staatsanwaltschaft des Kantons Solothurn vom 22. Januar 2015, wobei B.A._ mit einer teilbedingten Geldstrafe von 50 Tagessätzen à Fr. 30.-- sanktioniert wurde. B. Mit Verfügungen vom jeweils 23. März 2018 widerrief das Migrationsamt die Niederlassungsbewilligung von B.A._ und verweigerte die Verlängerung der Aufenthaltsbewilligung von A.A._ - jeweils wegen mutwilliger Verschuldung - und forderte sowohl B.A._ als auch A.A._ auf, die Schweiz bis zum 22. Juni 2018 zu verlassen. Der dagegen eingereichte, gemeinsame Rekurs blieb gemäss Entscheid des Justiz- und Sicherheitsdepartements des Kantons Basel-Stadt (Departement) vom 2. September 2019 erfolglos. Dessen Anfechtung mittels verwaltungsgerichtlichem Rekurs wurde gemäss Urteil des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht vom 9. Juni 2020 insofern teilweise gutgeheissen, als den Rekurrenten für das Rekursverfahren vor dem Departement die unentgeltliche Rechtspflege gewährt wurde. In der Hauptsache, nämlich bezüglich Widerruf der Niederlassungsbewlligung bzw. Nichtverlängerung der Aufenthaltsbewilligung, wurde der Rekurs jedoch abgewiesen. Die Vorinstanz gewährte B.A._ und A.A._ für das verwaltungsgerichtliche Rekursverfahren die unentgeltliche Rechtspflege. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 22. August 2020 beantragen A.A._ (Beschwerdeführerin) und B.A._ (Beschwerdeführer; beide gemeinsam: Beschwerdeführer) die Aufhebung des vorinstanzlichen Urteils. Eventualiter sei das [vorinstanzliche] Urteil "aufzuheben und rückzuweisen an diese Instanz zwecks Neubeurteilung." Die inhaltlich weitgehend identischen Verfügungen des Migrationsamts betreffend die beiden Rekurrenten vom 23. März 2018 seien aufzuheben. Die Aufenthaltsbewilligung der Beschwerdeführerin sei ihr zu belassen und um mindestens ein Jahr zu verlängern. Die Niederlassungsbewilligung des Beschwerdeführers sei ihm zu belassen. Ferner sei für das Bundesgerichtsverfahren den Beschwerdeführern weiterhin die unentgeltliche Rechtspflege zu bewilligen und der Beschwerde die aufschiebende Wirkung zu gewähren. Die Vorinstanz und das Departement beantragen mit ihren Vernehmlassungen jeweils die Abweisung der Beschwerde, während das Staatssekretariat für Migration auf eine Vernehmlassung verzichtet hat. Mit Verfügung vom 26. August 2020 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt. Am 31. August 2020 reichten die Beschwerdeführer eine weitere Eingabe ein, in der sie ihre Beschwerde als Verfassungsbeschwerde bezeichnen.