Sachverhalt: A. Gegen X._ läuft vor dem Betreibungsamt Bern-Mittelland, Dienststelle Mittelland, die Betreibung Nr. ... für eine Forderung aus einem Konkursverlustschein. Der Zahlungsbefehl vom 6. Mai 2010 wurde der Ehefrau von X._ am 10. Mai 2010 zugestellt; diese erhob sogleich Rechtsvorschlag. Mit Entscheid vom 2. August 2010 wurde der Gläubigerin Z._ die provisorische Rechtsöffnung erteilt. Der Entscheid erwuchs am 14. August 2010 in Rechtskraft. B. Mit Pfändungsankündigung vom 21. März 2012 teilte das Betreibungsamt X._ mit, dass am 30. März 2012 zwischen 10.00 und 12.00 Uhr an seiner Wohnadresse in A._ die Pfändung vollzogen werde. Mit Anzeige vom 4. April 2012 setzte das Betreibungsamt X._s Arbeitgeber davon in Kenntnis, dass gegen X._ am 30. März 2012 eine Lohnpfändung verfügt worden sei. Am 5. April 2012 (Datum des Poststempels) sandte das Betreibungsamt X._ eine Kopie dieser Lohnpfändungsanzeige, zusammen mit einer Berechnung des Existenzminimums. C. Mit Eingabe vom 18. April 2012 erhob X._ bei der Aufsichtsbehörde in Betreibungs- und Konkurssachen am Obergericht des Kantons Bern Beschwerde und beantragte in der Sache, die am 4. April 2012 verfügte Lohnpfändung aufzuheben und festzustellen, dass die Betreibung verjährt sei. Die Aufsichtsbehörde wies die Beschwerde ab, soweit sie darauf eintrat (Entscheid vom 13. Juli 2012). D. D.a Nun wendet sich X._ (Beschwerdeführer) an das Bundesgericht. In seiner Beschwerde vom 3. August 2012 stellt er das Begehren, den Entscheid der Aufsichtsbehörde vom 13. Juli 2012 und die Lohnpfändung vom 4. April 2012 aufzuheben. Weiter sei der Beschwerde die aufschiebende Wirkung zu erteilen. Schliesslich verlangt er eine angemessene Entschädigung für Umtriebe. D.b Das Bundesgericht erteilte der Beschwerde mit Verfügung vom 23. August 2012 die aufschiebende Wirkung. D.c In ihrer Stellungnahme vom 22. Oktober 2012 beantragt Z._ (Beschwerdegegnerin), die Beschwerde "vollumfänglich abzuweisen". Das Betreibungsamt Bern-Mittelland, Dienststelle Mittelland, hat auf eine Stellungnahme verzichtet, ebenso die Aufsichtsbehörde in Betreibungs- und Konkurssachen am Obergericht des Kantons Bern. Die Eingaben wurden dem Beschwerdeführer zur Wahrung des rechtlichen Gehörs zugestellt. 