Sachverhalt: A. Am 4. September 2008 ersuchte X._, Inhaber eines Garagenbetriebes, das Betreibungsamt Basel-Stadt um Auskunft, ob gegen Z._, wohnhaft in Basel, Betreibungen erfolgt und allenfalls offene Verlustscheine registriert seien. Für den Fall von Pfändungsvollzügen bat er um vollständige Auszüge bzw. Kopien der betreffenden Protokolle. Zur Glaubhaftmachung seines Interesses an der Auskunftserteilung reichte X._ den (vom Käufer unterzeichneten) Auto-Abzahlungskaufvertrag vom 4. Oktober 2007 ein. Das Betreibungsamt sandte ihm daraufhin am 5. September 2008 einen sogenannten detaillierten Betreibungsregisterauszug zu, der Angaben über die seit dem 1. Januar 2006 eingeleiteten Betreibungsverfahren enthält. Darin sind das Datum des Eingangs des jeweiligen Betreibungsbegehrens, der Name des Gläubigers, die Forderungshöhe, der Erledigungsvermerk, der Verfahrensstand, worunter der Stand des Zahlungsbefehls, des Verlustscheins sowie eine allfällige Lohnpfändung aufgeführt. Am 9. September 2008 verlangte X._ vom Betreibungsamt telefonisch die Angabe der weiter verlangten Details (Pfändungsprotokolle) über den betreffenden Betreibungsschuldner, was ihm das Amt jedoch verweigerte. B. Mit Beschwerde vom 9. September 2008 gelangte X._ an die kantonale Aufsichtsbehörde über das Betreibungs- und Konkursamt Basel-Stadt und verlangte, das Betreibungsamt sei anzuweisen, die Kopien der letzten zwei Pfändungsakten betreffend Z._ auszuhändigen. Mit Urteil vom 13. Oktober 2008 wies die kantonale Aufsichtsbehörde die Beschwerde ab. C. X._ führt mit Eingabe vom 6. April 2009 (Postaufgabe) Beschwerde in Zivilsachen gegen den (am 26. März 2009 zugestellten) kantonalen Beschwerdeentscheid. Der Beschwerdeführer verlangt im Wesentlichen, es sei der angefochtene Beschwerdeentscheid aufzuheben und das Betreibungsamt anzuweisen, Auskunft über die letzten beiden, gegenüber Z._ vollzogenen Pfändungen zu geben bzw. Einsicht in die betreffenden Protokolle zu gewähren. Das Betreibungsamt und die kantonale Aufsichtsbehörde haben auf eine Vernehmlassung verzichtet. Z._ hat sich nicht vernehmen lassen.