Sachverhalt: A. A.a. In der gegen X._ gerichteten Betreibung (Zahlungsbefehl Nr. ...) erteilte der Präsident des Zivilgerichts Basel-Stadt Z._, X._s früherer Ehefrau, am 10. September 2012 die definitive Rechtsöffnung für eine Betreibungsforderung von Fr. 35'711.90 (zzgl. Fr. 103.-- Betreibungskosten). Der Entscheid erging anlässlich einer mündlichen Verhandlung in Abwesenheit von X._, nachdem der Präsident des Zivilgerichts Basel-Stadt mit Verfügung vom 5. September 2012 die Verschiebungsgesuche beider Parteien mangels rechtsgenüglicher Entschuldigung abgewiesen hatte. A.b. Mit Schreiben vom 22. September 2012 (Datum der Postaufgabe) ersuchte X._ um unentgeltliche Rechtspflege und mit Schreiben vom 24. September 2012 (Datum der Postaufgabe) um schriftliche Begründung des Entscheids vom 10. September 2012. In der Folge trat der Präsident des Zivilgerichts mit Verfügung vom 27. September 2012 auf das Begehren um schriftliche Begründung nicht ein und stellte fest, dass der Rechtsöffnungsentscheid vom 10. September 2012 "per 20. September 2012 in Rechtskraft erwachsen sei". Überdies setzte der Präsident des Zivilgerichts X._ eine unerstreckbare Frist von 10 Tagen zur Präzisierung und Mitteilung, ob er die Eingabe vom 22. September 2012 als Wiederherstellungsgesuch im Sinn von Art. 148 ZPO einreichen wolle. Am 19. Oktober 2012 stellte X._ ein solches Gesuch. Dieses wies der Präsident des Zivilgerichts mit Entscheid vom 20. November 2012 ab. Die dagegen beim Appellationsgericht des Kantons Basel-Stadt erhobene Beschwerde blieb ohne Erfolg (Entscheid vom 7. März 2013). B. B.a. Mit Eingabe vom 9. April 2013 (Datum der Postaufgabe) erhebt X._ (Beschwerdeführer) Beschwerde in Zivilsachen. Er verlangt, "dass die Pfändung ab 1. Januar 2013 sistiert wird", und ersucht um kostenlose Prozessführung. Am 18. April 2013 teilte er dem Bundesgericht ferner mit, dass er vom 29. April 2013 bis zum 12. Mai 2013 in Kurferien sei. B.b. In ihrer Stellungnahme zum Gesuch des Beschwerdeführers um aufschiebende Wirkung vom 18. April 2013 beantragt Z._ (Beschwerdegegnerin) die Abweisung des Gesuchs. Unaufgefordert äussert sie sich auch zur Sache und beantragt die Abweisung der Beschwerde. Mit Verfügung vom 19. April 2013 wurde der Beschwerde die aufschiebende Wirkung zuerkannt.