Sachverhalt: A. A.a Das Betreibungsamt A._ pfändete in der von Y._ gegen Z._ geführten Betreibung Nr. qqq das pfändbare Einkommen ab 2. Mai 2001 bis 2. Mai 2002 (Pfändung Nr. 1) und erliess am 19. Juni 2001 die Pfändungsurkunde als provisorischen Verlustschein. Am 12. März 2003 rechnete das Betreibungsamt über die eingegangenen Lohnquoten ab. Es hielt den Erlös von Fr. 19'865.80 für die eingegangenen Lohnquoten Mai 2001 bis April 2002 zuzüglich Zins fest und errechnete zugunsten der Betreibungsgläubigerin Y._ einen Nettoerlös von Fr. 19'549.40, und nach Abzug des sofort ausbezahlten Teilbetrages (Fr. 13'500.--) einen Resterlös von Fr. 6'049.40. Gegen diese Abrechnung erhob X._ Beschwerde und verlangte, dass der Erlös der eingegangenen Lohnquoten ihm auszuzahlen sei, da seine gestützt auf die Abtretung vom 21. Januar 1999 erhobene Eigentumsansprache am gepfändeten Einkommen anerkannt worden sei. Das Bezirksgericht Bülach als untere kantonale Aufsichtsbehörde in Schuldbetreibungs- und Konkurssachen hiess die Beschwerde mit Beschluss (CB030009/U) vom 28. Juli 2003 gut und hob die Abrechnung des Betreibungsamtes vom 12. März 2003 über die Lohnpfändung in Pfändung Nr. 1 auf und wies das Betreibungsamt an, eine neue Abrechnung zu erstellen. A.b Mit Verfügung vom 15. Mai 2003 hielt das Betreibungsamt die Auszahlung in der ebenfalls gegenüber Z._ vollzogenen Pfändung Nr. 2 den auf die Betreibungsgläubigerin Y._ entfallenden Erlös vorläufig im Umfang der nach Pfändung Nr. 1 ausbezahlten Fr. 13'500.-- vorläufig - bis zum Abschluss des betreffenden Beschwerdeverfahrens - zurück. Gegen diese Verfügung erhob Y._ Beschwerde, welche die untere Aufsichtsbehörde mit Beschluss (CB030018/U) vom 28. Juli 2003 abwies, soweit darauf eingetreten wurde. B. Y._ erhob gegen beide erstinstanzlichen Beschlüsse Beschwerde. Das Obergericht des Kantons Zürich, II. Zivilkammer, als obere kantonale Aufsichtsbehörde in Schuldbetreibungs- und Konkurssachen hiess die Beschwerde gegen den Entscheid CB030009/U mit Beschluss vom 14. April 2004 gut und setzte die angefochtene Abrechnung über die Lohnpfändung wieder in Kraft (Dispositiv-Ziffer 1). Die Beschwerde gegen den Entscheid CB030018/U wurde mit gleichem Beschluss abgewiesen (Dispositiv-Ziffer 2). C. X._ hat den Beschluss der oberen Aufsichtsbehörde mit Beschwerdeschrift vom 3. Mai 2004 (rechtzeitig) an die Schuldbetreibungs- und Konkurskammer des Bundesgerichts weitergezogen und beantragt, Dispositiv-Ziffer 1 des angefochtenen Beschlusses sei aufzuheben und es sei - im Sinne der Erstinstanz - die Abrechnung des Betreibungsamtes vom 12. März 2003 über die Lohnpfändung in Pfändung Nr. 1 aufzuheben und das Betreibungsamt anzuweisen, eine neue Abrechnung zu erstellen und die eingegangenen Lohnquoten (Mai 2001 bis April 2002) ihm auszuzahlen. Weiter verlangt er aufschiebende Wirkung. Die obere Aufsichtsbehörde hat anlässlich der Aktenüberweisung auf Gegenbemerkungen (Art. 80 OG) verzichtet. Das Betreibungsamt hat sich nicht vernehmen lassen. Die Betreibungsgläubigerin als Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Mit Präsidialverfügung vom 10. Mai 2004 wurde der Beschwerde aufschiebende Wirkung zuerkannt.