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.

Erwägungen:
1. 1.1 Entscheide kantonaler Aufsichtsbehörden über Beschwerden gegen Verfügungen von Vollstreckungsorganen gemäss <ref-law> unterliegen der Beschwerde in Zivilsachen (<ref-law> i.V.m. <ref-law>). Das Rechtsmittel ist unabhängig von einer gesetzlichen Streitwertgrenze zulässig (<ref-law>). Als Pfändungsschuldner ist der Beschwerdeführer zur Anfechtung des Entscheides, mit dem die kantonale Aufsichtsbehörde seine Beschwerde abgewiesen hat, legitimiert (<ref-law>). Auch hat er die Beschwerde fristgerecht (<ref-law>) erhoben. Auf die Beschwerde ist demnach einzutreten.
1.2 Mit der Beschwerde in Zivilsachen kann u.a. die Verletzung von Bundesrecht einschliesslich des Bundesverfassungsrechts sowie von Völkerrecht gerügt werden (Art. 95 lit. a und b BGG). Das Bundesgericht wendet das Recht in diesem Bereich von Amtes wegen an (<ref-law>) und prüft mit freier Kognition, ob der angefochtene Entscheid Recht verletzt.
2. Der Beschwerdeführer bemängelt in verschiedener Hinsicht die Art und Weise der Durchführung des Pfändungsverfahrens in der Betreibung Nr. ... vor dem Betreibungsamt Bern-Mittelland, Dienststelle Mittelland.
2.1 So stört sich der Beschwerdeführer daran, dass ihm die Mitteilungen des Betreibungsamtes entgegen <ref-law> weder durch eingeschriebenen Brief noch durch Übergabe gegen Empfangsbestätigung zugestellt wurden. Inwiefern er allein dadurch einen konkreten Nachteil erlitten hätte, tut der Beschwerdeführer jedoch in keiner Weise dar. Nun ist es aber nicht Aufgabe des Bundesgerichts, hinsichtlich der Formalien der Zustellung betreibungsamtlicher Mitteilungen einzugreifen, wenn der geschilderte Fehler ohne erkennbare praktische Relevanz ist.
2.2 Weiter hält der Beschwerdeführer dem angefochtenen Entscheid entgegen, es sei sachverhaltsmässig nicht bewiesen, dass die Gläubigerin am 21. September 2010 überhaupt das Fortsetzungsbegehren gestellt habe. Die Gläubigerin habe lediglich nachweisen können, der Post am besagten Tag einen Briefumschlag übergeben zu haben. Dass in diesem Umschlag auch tatsächlich das Fortsetzungsbegehren war, sei jedoch nicht erstellt. Mit dieser Sachverhaltsrüge ist der Beschwerdeführer vor Bundesgericht mangels materieller Erschöpfung des Instanzenzuges nicht zu hören, denn vor der kantonalen Aufsichtsbehörde hat er nicht bestritten, dass die Gläubigerin am 21. September 2010 der Post tatsächlich ihr Fortsetzungsbegehren übergeben hatte. Um den vorinstanzlich festgestellten Sachverhalt in dieser Hinsicht anzugreifen, müsste der Beschwerdeführer dartun, dass die Vorinstanz ihn offensichtlich unrichtig, das heisst in Verletzung des Willkürverbots (<ref-law>) festgestellt hat (Botschaft, BBl 2001 IV 4338; <ref-ruling> E. 1.2.2 S. 252; <ref-ruling> E. 7.1 S. 398); für die Geltendmachung von Grundrechtsverletzungen gilt das Rügeprinzip (<ref-law>). Untersteht die vorgetragene Sachverhaltsrüge im Verfahren der Beschwerde in Zivilsachen dem Rügeprinzip, so ergibt sich aus dem Erfordernis der Letztinstanzlichkeit des angefochtenen Entscheides (<ref-law>), dass die rechtssuchende Partei die ihr bekannten rechtserheblichen Einwände der Vorinstanz nicht vorenthalten darf, um sie erst nach dem Ergehen eines ungünstigen Entscheides im anschliessenden Rechtsmittelverfahren zu erheben (<ref-ruling> E. 2 S. 640 mit Hinweisen).
2.3 Für den - nun eingetretenen (E. 2.2) - Fall, dass das Fortsetzungsbegehren als rechtzeitig gestellt zu gelten hat, hält der Beschwerdeführer auch vor Bundesgericht daran fest, dass die Gläubigerin "ihr Vollstreckungsrecht" verwirkt habe, weil sie sich beim Betreibungsamt erst im März 2012 nach dem Stand des Verfahrens erkundigt und es damit versäumt habe, "rechtzeitig auf den tatsächlichen Pfändungsvollzug hinzuwirken". Das überlange Zuwarten sei "als Rückzug der Betreibung zu qualifizieren"; die Gläubigerin hätte wegen Rechtsverzögerung oder -verweigerung eine Beschwerde erheben müssen. Die Aufsichtsbehörde führt in diesem Zusammenhang aus, es könne nicht der Gläubigerin angelastet werden, wenn die Dienststelle das Fortsetzungsbegehren nicht bzw. nicht korrekt behandelt habe. Handlungen von Dritten - namentlich das Verhalten der Gläubiger - würden überdies keine Verfügungen im Sinne von <ref-law> darstellen und könnten daher auch nicht zum Gegenstand eines betreibungsrechtlichen Beschwerdeverfahrens gemacht werden. Der Beschwerdeführer setzt sich mit all diesen Erwägungen in keiner Weise auseinander. Damit verkennt er die in <ref-law> vorgesehene Pflicht, wonach in der Begründung in gedrängter Form darzulegen ist, inwiefern der angefochtene Akt Recht verletzt. Der Beschwerdeführer muss in seiner Rechtsschrift an das Bundesgericht auf den angefochtenen Entscheid eingehen und im Einzelnen aufzeigen, worin eine Verletzung von Bundesrecht liegt. Er soll im Schriftsatz mit seiner Kritik an den Erwägungen der Vorinstanz ansetzen, die er als rechtsfehlerhaft erachtet (vgl. <ref-ruling> E. 2a S. 400; Urteil 4A_22/ 2008 vom 10. April 2008 E. 1). Mit der blossen Wiederholung der bereits vor der Aufsichtsbehörde vorgetragenen Einwände ist es also nicht getan. Im Übrigen verfängt sich der Beschwerdeführer auch in Widersprüche, wenn er der Gläubigerin empfiehlt, gegen den Kanton Bern eine "Haftungsklage" anzustrengen. Denn damit bringt er zum Ausdruck, dass die Verzögerung in der Fortsetzung der Betreibung auch seiner Meinung nach dem Betreibungsamt vorzuwerfen ist.
2.4 Auf der nächsten Stufe seiner Argumentationskaskade beanstandet der Beschwerdeführer, das Betreibungsamt selbst habe durch "eigenes Untätigkeitsein seine Amtspflicht" verletzt, indem es das Fortsetzungsbegehren während über eineinhalb Jahren nicht behandelt und erst auf Intervention der Gläubigerin hin reagiert habe. Die Aufsichtsbehörde weist in diesem Kontext auf <ref-law> hin, wonach das Betreibungsamt nach Empfang des Fortsetzungsbegehrens unverzüglich die Pfändung zu vollziehen hat, und hält unter Hinweis auf <ref-ruling> fest, hierbei handle es sich lediglich um eine Ordnungsfrist, weshalb die Pfändung weder nichtig noch anfechtbar sei, wenn der Pfändungsvollzug nicht unverzüglich erfolge. Diese Beurteilung der Rechtslage ist zutreffend. Zwar lag der in <ref-ruling> E. 2a S. 89 f. veröffentlichten Rechtsprechung die ursprüngliche Fassung von <ref-law> zugrunde, die bis am 31. Dezember 1996 in Kraft war und dem Betreibungsbeamten vorschrieb, die Pfändung innerhalb von drei Tagen nach Eingang des Fortsetzungsbegehrens zu vollziehen (s. AS 11 552; BS 3 22). Die zitierte Rechtsprechung muss aber sinngemäss auch für die aktuelle Fassung von <ref-law> gelten, sollte mit der Gesetzesanpassung doch gerade den in der Praxis aufgetretenen Schwierigkeiten beim fristgerechten Pfändungsvollzug Rechnung getragen werden (Botschaft über die Änderung des Bundesgesetzes über Schuldbetreibung und Konkurs [SchKG] vom 8. Mai 1991, BBl 1991 III 73). Demnach ist auch der Ausdruck "unverzüglich" im Sinne einer blossen Ordnungsfrist zu verstehen. Daraus folgt, dass eine Säumnis des Betreibungsamtes beim Vollzug der Pfändung die Gültigkeit des Verfahrens nicht berührt. Von vornherein unbehelflich ist der Einwand des Beschwerdeführers, anders als im Fall, den das Bundesgericht im besagten Entscheid zu beurteilen hatte, sei er seit der Zustellung des Rechtsöffnungsentscheids am 2. August 2010 bis zum Pfändungsvollzug vom 30. März 2012 jederzeit erreichbar gewesen. Für die Beantwortung der Frage, ob das Betreibungsamt die Pfändung im Sinne von <ref-law> unverzüglich vollzogen hat, kann es schon unter dem Gesichtspunkt der Rechtssicherheit nicht darauf ankommen, ob der Betriebene im konkreten Fall erreichbar war. Die Beschwerde erweist sich insofern als unbegründet.
2.5 Schliesslich stellt sich der Beschwerdeführer auf den Standpunkt, die Pfändung sei insgesamt nichtig, weil es an einer gegenüber ihm als Schuldner erfolgten gültigen Pfändungserklärung fehle. Die blosse Zustellung der Kopie der Lohnpfändungsanzeige samt Berechnung des Existenzminimums (Sachverhalt Bst. B) vermöge eine Pfändungserklärung nicht zu ersetzen. Sollte die Mitteilung vom 4. April 2012 dennoch als Pfändungserklärung betrachtet werden, dann stelle sie eine Betreibungshandlung dar. Diesfalls wäre der Vollzug der Pfändung jedenfalls in den Betreibungsferien erfolgt, denn die Mitteilung sei ihm am Ostersamstag 2012 zugestellt worden; dies führe ebenfalls zur Ungültigkeit.
2.5.1 Unter welchen Voraussetzungen eine Lohnpfändung als vollzogen zu gelten hat, ist eine Rechtsfrage, die das Bundesgericht frei prüft (E. 1.2). Wesentliches Element der Pfändung ist die in <ref-law> vorgesehene Erklärung des Betreibungsbeamten an den Schuldner, dass dieser bei Straffolge ohne Bewilligung des Betreibungsbeamten nicht über die gepfändeten Vermögensstücke verfügen darf. Solange der Betreibungsschuldner nicht ausdrücklich auf die gesetzliche Unterlassungspflicht hingewiesen worden ist, entfaltet die Pfändung keine Wirkung und ist sie auch nicht rechtsgültig vollzogen (<ref-ruling> E. 1.2 S. 663 f. mit Hinweisen). Das in der Pfändung herrschende Spezialitätsprinzip gebietet, dass Vermögensbestandteile des Schuldners nur dann wirksam gepfändet werden können, wenn sie individualisiert sind, und dass deshalb dem Schuldner ohne deren klare Bezeichnung auch nicht im Sinne von <ref-law> bei Straffolge verboten werden kann, darüber zu verfügen (BGE 50 III 192 S. 195; vgl. auch <ref-ruling> E. 5a S. 16). Entsprechend ist auch die Pfändungserklärung gemäss <ref-law> nur wirksam, wenn der Schuldner konkret, das heisst mit Bezug auf bestimmte, klar bezeichnete Vermögensstücke auf das Verfügungsverbot und auf die Straffolge von <ref-law> aufmerksam gemacht wird (<ref-ruling> E. 3 S. 22). Für die Lohnpfändung bedeutet dies, dass der Betreibungsbeamte dem Schuldner unter Hinweis auf das Verbot und die Straffolgen einer vom Amte nicht bewilligten Verfügung ausdrücklich zu erklären hat, ein bestimmter Betrag seines Erwerbseinkommens sei gepfändet (<ref-ruling> E. 3a S. 80; <ref-ruling> E. 1 S. 36). Der Schuldner hat einen unabdingbaren Anspruch darauf, dass ihm gleichzeitig mit dem Inkrafttreten der Verdienstpfändung mitgeteilt wird, wie die pfändbare Quote ermittelt worden ist. Dazu gehört auch die Bekanntgabe der Berechnung des Notbedarfs (<ref-ruling> E. 2 S. 15). Die Anzeige an den Arbeitgeber, die gemäss <ref-law> zu erlassen ist, wenn der Schuldner eine unselbständige Erwerbstätigkeit ausübt (obligatorisches Formular Nr. 10), ist hingegen grundsätzlich nicht ein wesentlicher Bestandteil des Pfändungsvollzugs. Vielmehr handelt es sich um eine Sicherungsmassnahme, die zum Pfändungsvollzug hinzutritt (<ref-ruling> E. 3a S. 80 f.; <ref-ruling> E. 1 S. 36 mit Hinweisen).
2.5.2 Dem angefochtenen Entscheid zufolge ist die Pfändung am 30. März 2012 erfolgt. Auch in der Lohnpfändungsanzeige vom 4. April 2012 ist vermerkt, dass gegen den Beschwerdeführer "am 30.03.2012 eine Lohnpfändung verfügt worden" sei (s. Sachverhalt Bst. B). Welche Erklärungen der Betreibungsbeamte gegenüber dem Beschwerdeführer an diesem Tag tatsächlich abgegeben hat, lässt sich dem angefochtenen Entscheid nicht entnehmen und geht auch nicht aus den Akten hervor. Offenkundig konnte dem Beschwerdeführer an diesem Tag jedoch nicht unter Angabe der Berechnung seines Notbedarfs eröffnet worden sein, welcher bestimmte Betrag seines Lohnes gepfändet sei. Dies ergibt sich aus dem mit "Existenz-Minimum" betitelten Dokument, das dem Beschwerdeführer zusammen mit der Lohnpfändungsanzeige zugestellt wurde. Auf diesem Schriftstück gibt das Betreibungsamt den Zeitpunkt der Berechnung des Notbedarfs mit dem 4. April 2012 an. War aber am 30. März 2012 die pfändbare Quote noch nicht festgelegt, so konnte die Pfändung nach dem in Erwägung 2.5.1 Ausgeführten jedenfalls an diesem Tag nicht wirksam vollzogen worden sein. Soweit die Aufsichtsbehörde vom Gegenteil ausgeht, ist dies unzutreffend. Dasselbe gilt für die entsprechende Angabe in der Lohnpfändungsanzeige.
2.5.3 Nachdem allein die Lohnpfändungsanzeige einen ordentlichen Pfändungsvollzug nicht zu ersetzen vermag (E. 2.5.1), stellt sich die Frage, ob hierzu die Zustellung der erwähnten Notbedarfsberechnung taugt. Dieses vom Betreibungsbeamten unterzeichnete Schriftstück enthält Angaben zur Person des Schuldners; es nennt die Höhe seines Lohnes und die einzelnen Bedarfsposten, aus deren Gegenüberstellung mit dem Einkommen die pfändbare Lohnquote errechnet wird. Unter der Überschrift "Verfügung" steht geschrieben, es werde derjenige Betrag gepfändet, der das Existenzminimum von Fr. 5'035.45 pro Monat übersteigt, wobei als Datum der Verfügung der 4. April 2012 aufgeführt ist. Indessen fehlt der in <ref-law> vorgeschriebene ausdrückliche Hinweis an den Schuldner, dass er bei Straffolge ohne Bewilligung des Betreibungsbeamten nicht über den das Existenzminimum überschreitenden Monatslohn verfügen dürfe. Zwar ist die in <ref-law> enthaltene Vorschrift auf der Pfändungsankündigung abgedruckt. Dies genügt aber nicht, denn mit deren Erhalt weiss der Schuldner noch nicht, ob und gegebenenfalls welche seiner Vermögensstücke gepfändet werden. Wie es sich verhielte, wenn dem Beschwerdeführer anlässlich des Pfändungstermins am 30. März 2012 mitgeteilt worden wäre, dass der aus der noch zuzustellenden Kopie der Existenzminimumberechnung zu entnehmende Betrag als gepfändet zu gelten habe und er - unter Hinweis auf die Straffolge - über diese Quote ohne Bewilligung nicht mehr verfügen dürfe, kann offenbleiben. Denn das Betreibungsamt macht weder in seiner Vernehmlassung an die Aufsichtsbehörde noch in seiner Stellungnahme an das Bundesgericht geltend, den Beschwerdeführer am 30. März 2012 in diesem Sinne vorab instruiert zu haben. Schliesslich erübrigt sich bei der Pfändung von Forderungen die beschriebene ausdrückliche Erklärung an den Betriebenen auch nicht damit, dass dem Schuldner des Betriebenen - hier dem Arbeitgeber - nach <ref-law> angezeigt wird, er könne rechtsgültig nur noch an das Betreibungsamt leisten. Im Umfang, in welchem der angewiesene Drittschuldner direkt an das Betreibungsamt leistet, kann der Betriebene auf die Leistung, die ihm der Dritte schuldet, zwar tatsächlich nicht mehr zugreifen. Als blosse Sicherungsmassnahme hat die Anweisung nach <ref-law> indessen nicht zur Folge, dass die gepfändete Forderung zivilrechtlich an das Betreibungsamt übergeht. Entrichtet der Drittschuldner seine Leistung in Missachtung der Anweisung an den Betriebenen, so könnte dieser mangels eines gültigen Verfügungsverbotes als Gläubiger der gepfändeten Forderung über die ihm erbrachte Leistung verfügen, und der betreibende Gläubiger hätte das Risiko zu tragen, wenn der Drittschuldner kein zweites Mal leistet (BGE 67 III 22 S. 24).
2.5.4 Dem Beschwerdeführer ist also darin beizupflichten, dass das Betreibungsamt die Pfändung, die es auf den 30. März 2012 angekündigt hatte, allein mit der Zustellung der Lohnpfändungsanzeige und der Berechnung des Existenzminimums, beide datierend vom 4. April 2012, nicht rechtsgültig vollziehen konnte. Die Beschwerde erweist sich insofern als begründet. Zu widersprechen ist dem Beschwerdeführer hingegen, wenn er daraus den Schluss zieht, die Pfändung sei "insgesamt nichtig". Vielmehr folgt aus dem Gesagten lediglich, dass die Pfändung aufgrund der im vorliegenden Prozess streitigen und aktenkundigen betreibungsamtlichen Anordnungen noch keine Wirkung entfalten konnte. Ist der Schuldner an der Pfändung weder anwesend noch vertreten, so tritt die Wirkung der Pfändung erst dann ein, wenn der Vollzug dem Schuldner mitgeteilt wurde, was namentlich durch die Zustellung der Pfändungsurkunde geschehen kann (<ref-ruling> E. 5a S. 16, bestätigt in <ref-ruling> E. 1.2 S. 663; vgl. auch <ref-ruling> E. 4 S. 115). In diesem Fall müsste freilich auch die Pfändungsurkunde - neben den Angaben gemäss <ref-law> - die in <ref-law> vorgeschriebene Pfändungserklärung enthalten (s. JEAN-CLAUDE MATHEY, La saisie de salaire et de revenu, Tolochenaz 1989, S. 133 f.). Ob dem Beschwerdeführer der Vollzug der Pfändung inzwischen mit einer solchen Pfändungsurkunde oder mit einer anderen, den beschriebenen Anforderungen genügenden Verfügung eröffnet worden ist, muss hier offenbleiben. Denn welche weiteren Verfügungen das Betreibungsamt seit der Zustellung der Lohnpfändungsanzeige samt Existenzminimum-Berechnung allenfalls getroffen hat, ist nicht Gegenstand des vorliegenden Prozesses.
3. 3.1 Gestützt auf die vorstehenden Erwägungen ist die Beschwerde gutzuheissen und der angefochtene Entscheid aufzuheben. Das Bundesgericht stellt fest, dass vor dem 7. April 2012 - dem Tag, an welchem dem Beschwerdeführer das Schreiben des Betreibungsamts vom 4. April 2012 unbestrittenermassen zugestellt wurde - in der Betreibung Nr. ... keine gültige Pfändung vollzogen wurde. Bei diesem Ausgang des Verfahrens obsiegt der Beschwerdeführer. Als unterliegende Partei hat die Beschwerdegegnerin, die sich dem angefochtenen Entscheid vorbehaltlos anschliesst, für die Gerichtskosten aufzukommen (<ref-law>). Dem Betreibungsamt sind keine Gerichtskosten aufzuerlegen (<ref-law>).
3.2 Der - anwaltlich nicht vertretene - Beschwerdeführer verlangt eine Entschädigung für die Umtriebe, die ihm dadurch entstanden seien, dass ihm der angefochtene Entscheid während der Betreibungsferien zugestellt wurde. Er sei im Ausland in den Ferien gewesen; die Zustellung habe hohe Telefon- und Mobilfunkkosten nach sich gezogen. Nach <ref-law> hat die obsiegende Partei in der Regel Anspruch auf Ersatz aller durch den Rechtsstreit verursachten notwendigen Kosten. Neben den Anwaltskosten, die hier nicht in Frage stehen, umfasst die Parteientschädigung die allfälligen weiteren notwendigen Kosten, die durch den Rechtsstreit verursacht werden (Art. 1 lit. b des Reglements über die Parteientschädigung und die Entschädigung für die amtliche Vertretung im Verfahren vor dem Bundesgericht vom 31. März 2006 (SR 173.110.210.3). Nun war die Zustellung des angefochtenen Entscheids aber nicht abhängig davon, dass der Beschwerdeführer an das Bundesgericht gelangte. Vielmehr ist dieser Vorgang dem kantonalen Verfahren zuzuordnen. Daher können die geltend gemachten "Umtriebe" nicht im Sinne der zitierten Vorschriften als durch den vor Bundesgericht geführten Rechtsstreit verursacht gelten. Das Begehren ist aus diesem Grund abzuweisen. Allfällige Schadenersatzansprüche gegen den Kanton Bern wären vor der zuständigen kantonalen Instanz geltend zu machen. Immerhin ist anzumerken, dass Entscheide der kantonalen Aufsichtsbehörden nicht als Betreibungshandlungen im Sinne von <ref-law> gelten, soweit die Behörde darin lediglich über die Begründetheit der Beschwerde befindet, ohne dem Betreibungsbeamten die Vornahme einer Betreibungshandlung vorzuschreiben oder den Parteien eine Frist anzusetzen und damit die Schuldbetreibung in ein vorgerücktes Stadium zu bringen (<ref-ruling> E. 1b S. 13 f., bestätigt in Urteil 7B.3/2005 vom 12. Januar 2005 E. 1.3.2). Dass ihm im bundesgerichtlichen Verfahren selbst ein entschädigungspflichtiger Aufwand entstanden wäre, macht der Beschwerdeführer nicht geltend.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid des Obergerichts des Kantons Bern, Aufsichtsbehörde in Betreibungs- und Konkurssachen, vom 13. Juli 2012 wird aufgehoben. Es wird festgestellt, dass vor dem 7. April 2012 in der Betreibung Nr. ... des Betreibungsamtes Bern-Mittelland, Dienststelle Mittelland, keine gültige Pfändung vollzogen wurde.
2. Die Gerichtskosten von Fr. 500.-- werden der Beschwerdegegnerin auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien, dem Betreibungsamt Bern-Mittelland, Dienststelle Mittelland, und dem Obergericht des Kantons Bern, Aufsichtsbehörde in Betreibungs- und Konkurssachen, schriftlich mitgeteilt.
Lausanne, 21. November 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: V. Monn