Sachverhalt: A. Der Einzelrichter des Kantonsgerichts von Appenzell A.Rh. als Arrestrichter befahl am 2. September 2003 dem Betreibungsamt Appenzeller Vorderland, für den Gläubiger X._ "sämtliche Erbansprüche von Y._ [Schuldner] gegenüber der Erbengemeinschaft Z._ sel., verstorben am 14. Juli 2003 in A._" zu verarrestieren (Arrestbefehl Nr. ...). Am 22. September 2003 vollzog das Betreibungsamt den Arrest wie befohlen (Arresturkunde vom 25. September 2003). Gegen den Zahlungsbefehl in der von X._ eingeleiteten (Arrestprosequierungs-) Betreibung Nr. ... erhob Y._ (Teil-) Rechtsvorschlag nur in Bezug auf die Zinsen der in Betreibung gesetzten Forderung von Fr. 50'000.--. Am 5. November 2003 stellte X._ das Fortsetzungsbegehren. In der Folge vollzog das Betreibungsamt am 16. Dezember 2003 die Pfändung, indem es den Lohn von Y._ pfändete, indessen keine pfändbare Lohnquote feststellen konnte und einen provisorischen Verlustschein erliess (Pfändungsurkunde vom 20. Januar 2004). B. Gegen die Pfändungsurkunde vom 20. Januar 2004 erhob X._ Beschwerde und verlangte die Pfändung der Erbansprüche von Y._. Mit Entscheid vom 23. März 2004 hiess das Obergericht von Appenzell A.Rh. als Aufsichtsbehörde für Schuldbetreibung und Konkurs die Beschwerde teilweise gut; sie hob die angefochtene Pfändungsurkunde auf und wies das Betreibungsamt an, eine neue Pfändungsurkunde "im Sinne der Erwägungen" auszufertigen (Dispositiv-Ziffer 1). C. X._ hat den Beschluss der kantonalen Aufsichtsbehörde mit Beschwerdeschrift vom 10. Mai 2004 (rechtzeitig) an die Schuldbetreibungs- und Konkurskammer des Bundesgerichts weitergezogen und beantragt, der angefochtene Entscheid sei aufzuheben und das Betreibungsamt sei anzuweisen, die Erbansprüche von Y._ zu pfänden. Die Aufsichtsbehörde hat anlässlich der Aktenüberweisung auf Gegenbemerkungen (Art. 80 OG) verzichtet. Der Betreibungsschuldner Y._ beantragt die Abweisung der Beschwerde. Zugleich stellt er das Gesuch um unentgeltliche Rechtspflege. Das Betreibungsamt hat auf eine Stellungnahme verzichtet. 