Sachverhalt: A. A.a Im Konkurs über X._ erhielt die Bank Y._ einen Verlustschein im Betrag von Fr. 197'715.65. Gestützt auf den Konkursverlustschein leitete die Bank beim Betreibungsamt der Stadt-Basel die Betreibung ein, worauf X._ Rechtsvorschlag erhob mit der Begründung, sie sei nicht zu neuem Vermögen gekommen. Am 26. August 2008 stellte das Zivilgericht Basel-Stadt fest, dass X._ mit Bezug auf die Betreibung Nr. 1 vom 14. April 2008 im Umfang von Fr. 13'400.-- zu neuem Vermögen gekommen ist, und verweigerte im gleichen Umfang den Rechtsvorschlag in der erwähnten Betreibung; im diesen Betrag übersteigenden Umfang wurde der Rechtsvorschlag mangels neuen Vermögens bewilligt. Gestützt auf dieses Urteil (sowie nach Rückzug des ordentlichen Rechtsvorschlages) verlangte die Bank die Fortsetzung der Betreibung im Umfang von Fr. 13'400.--. A.b Am 26. Februar 2009 vollzog das Betreibungsamt gegenüber X._ in der von der Bank eingeleiteten Betreibung die Pfändung. Dabei wurde das Existenzminimum der Schuldnerin auf Fr. 4'553.-- festgesetzt und ihr darüber liegendes Einkommen im Umfang von monatlich Fr. 3'140.-- gepfändet (Pfändungsurkunde vom 7. April 2009). B. Gegen die Pfändung erhob X._ Beschwerde und verlangte, die Lohnpfändung sei auf monatlich Fr. 1'116.-- herabzusetzen, im Wesentlichen mit der Begründung, die Pfändung des festgestellten neuen Vermögens von Fr. 13'400.-- sei anteilsmässig auf das Lohnpfändungsjahr zu verteilen. Die Aufsichtsbehörde über das Betreibungs- und Konkursamt Basel-Stadt wies die Beschwerde mit Urteil vom 19. Mai 2009 ab. C. Mit Eingabe vom 21. September 2009 (Postaufgabe) hat X._ Beschwerde in Zivilsachen erhoben. Die Beschwerdeführerin beantragt dem Bundesgericht, das Urteil der kantonalen Aufsichtsbehörde sei aufzuheben und die Lohnpfändung auf monatlich Fr. 1'116.-- festzusetzen. Weiter ersucht sie um unentgeltliche Rechtspflege. Die kantonale Aufsichtsbehörde hat auf eine Vernehmlassung verzichtet. Die Bank Y._ (Beschwerdegegnerin) beantragt die Abweisung der Beschwerde