Sachverhalt:
A. A.a Das Betreibungsamt Olten-Gösgen stellte in den gegen X._ durchgeführten Betreibungen gestützt auf <ref-law> die Verlustscheine vom 31. Mai 2000 (VS-Nr. 52699), 27. September 2002 (VS-Nr. 75187), 5. Juni 2003 (VS-Nr. 82290) und 27. November 2007 (VS-Nr. 122'468) aus.
A.b Am 24. Februar 2011 gelangte X._ an das Betreibungsamt und verlangte für die Betreibungen, welche zu den erwähnten Verlustscheinen geführt hatten, "eine detaillierte Kostenzusammenstellung".
A.c Mit Verfügung vom 7. März 2011 wies das Betreibungsamt das Gesuch um Einsichtnahme in die detaillierten Kostenbelege und/oder Zusammenstellungen ab.
B. Gegen die Verfügung des Betreibungsamtes gelangte X._ an die Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn, welche die Beschwerde mit Urteil vom 14. April 2011 abwies, soweit darauf eingetreten wurde.
C. Mit Eingabe vom 12. Mai 2011 hat X._ Beschwerde in Zivilsachen erhoben. Der Beschwerdeführer beantragt dem Bundesgericht, das Urteil der kantonalen Aufsichtsbehörde aufzuheben und das Betreibungsamt anzuweisen, Akteneinsicht zu gewähren. Weiter verlangt er den Ausstand der Bundesrichter Féraud und Zünd sowie die Gewährung der unentgeltlichen Rechtspflege.
Die kantonale Aufsichtsbehörde sowie das Betreibungsamt beantragen die Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1. Das Ausstandsbegehren (<ref-law>) des Beschwerdeführers ist gegenstandslos, weil Bundesrichter Féraud nicht mehr im Amt ist und Bundesrichter Zünd mit der vorliegenden Sache nicht befasst ist. Soweit der Ausstand von "solothurnischen Mitgliedern" des Bundesgerichts verlangt wird, kann auf ein derartiges, nur allgemein gehaltenes Ablehnungsbegehren nicht eingetreten werden (vgl. <ref-ruling> E. 2; <ref-ruling> E. 1c und d).
2. 2.1 Entscheide kantonaler Aufsichtsbehörden über Verfügungen der Vollstreckungsorgane gemäss <ref-law> unterliegen der Beschwerde in Zivilsachen (<ref-law> i.V.m. <ref-law>). Sie ist unabhängig von einer gesetzlichen Streitwertgrenze gegeben (<ref-law>).
2.2 Der Beschwerdeführer hat grundsätzlich ein schutzwürdiges Interesse an der Aufhebung bzw. Änderung des angefochtenen Entscheides (<ref-law>). Die Beschwerde gegen die verfahrensabschliessende Entscheidung (<ref-law>) ist fristgemäss erhoben worden (<ref-law>) und grundsätzlich zulässig.
2.3 Mit vorliegender Beschwerde kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>).
3. Die Aufsichtsbehörde hat im Wesentlichen erwogen, dass die betreffenden Verlustscheine aus den Jahren 2000, 2002, 2003 und 2007 rechtskräftig seien. Für den Beschwerdeführer bestehe kein gegenwärtiges Interesse mehr, diesbezüglich eine detaillierte Kostenaufstellung zu erhalten, zumal offenbar keine weiteren Belege vorhanden seien und das Begehren rechtsmissbräuchlich erscheine.
Der Beschwerdeführer hält demgegenüber fest, dass er Einsicht in die Akten des Betreibungsamtes "für den Beweis der Nichtigkeit" der Verlustscheine benötige. Die Verweigerung der Akteneinsicht verstosse gegen <ref-law> und <ref-law>.
4. Nach den Sachverhaltsfeststellungen der Aufsichtsbehörde wurden die Betreibungen durch definitive Verlustscheine (<ref-law>) vom 31. Mai 2000, 27. September 2002, 5. Juni 2003 und 27. November 2007 formell zum Abschluss gebracht. Die Akten erledigter Betreibungen dürfen nach Ablauf von 10 Jahren, vom Tage der Erledigung an gerechnet, vernichtet werden; die Betreibungsbücher (nebst den zugehörigen Personenregistern) sind während 30 Jahren seit deren Abschluss aufzubewahren (Art. 2 der Verordnung über die Aufbewahrung der Betreibungs- und Konkursakten vom 5. Juni 1996; VABK, SR 281.33). Im Betreibungsbuch werden u.a. die Gebühren und Kosten eingetragen (Art. 10 Abs. 6 und Art. 17 Abs. 1 Ziff. 1 der Verordnung über die im Betreibungs- und Konkursverfahren zu verwendenden Formulare und Register sowie Rechnungsführung vom 5. Juni 1996; VFRR, SR 281.31). Diese Grundlagen stehen nicht in Frage. Umstritten ist vorliegend das Recht auf Einsicht in Dokumente der erledigten Betreibungen.
4.1 Das Recht Dritter, in die Protokolle und Register der Betreibungs- und Konkursämter einzusehen und sich Auszüge daraus geben zu lassen, erlischt fünf Jahre nach Abschluss des Verfahrens (<ref-law>). Von dieser Regel sind die einstigen Parteien des Zwangsvollstreckungsverfahrens ausgenommen. Hier wird das ein Interesse voraussetzende Einsichtsrecht grundsätzlich durch die Dauer der amtlichen Pflicht zur Aufbewahrung der Akten begrenzt (<ref-ruling> E. 4 S. 51). Sofern die Betreibungs- oder Konkursakten noch vorhanden sind, kann auch nach Ablauf der amtlichen Aufbewahrungsfrist noch Einsicht verlangt werden (<ref-ruling> E. 3.2 S. 43 ff.).
4.2 Vorliegend ist die Aufbewahrungsfrist für die Betreibungsbücher für alle vier in Frage stehenden Betreibungen noch nicht abgelaufen; das Gleiche gilt für die Aufbewahrungsfrist für die Akten der drei zuletzt erledigten Betreibungen. Einzig für die mit Verlustschein vom 31. Mai 2000 erledigte Betreibung war im Zeitpunkt (24. Februar 2011), in welchem der Beschwerdeführer das Einsichtsgesuch stellte, die 10-jährige Aufbewahrungspflicht der Betreibungsakten bereits abgelaufen. Indessen kann die Aufsichtsbehörde mit dem blossen Hinweis, es seien "[beim Betreibungsamt] keine weiteren Belege vorhanden", das Recht auf Akteneinsicht nicht verweigern. Abgesehen davon, dass die Vorinstanz nicht erläutert, dass Dokumente vernichtbar und vernichtet sein sollen, wird lediglich die Darstellung des Betreibungsamtes in dessen Vernehmlassung im kantonalen Verfahren übernommen. Die Aufsichtsbehörde vermengt das Interesse an der Einsicht mit der Frage, ob und welche Akten tatsächlich vorliegen, was indessen Ergebnis der Gewährung der Akteneinsicht ist. Ebenso wenig kann (wie das Betreibungsamt offenbar meint) die Akteneinsicht mit der Begründung verweigert werden, die Betreibungen bzw. deren Kosten seien in rechtskonformer Weise registriert worden. Im Rahmen der Akteneinsicht geht es nicht um die Würdigung der Protokolle und Belege durch die Betreibungs- und Konkursämter (<ref-ruling> E. 4 S. 51). Entscheidend ist einzig, ob der Beschwerdeführer ein hinreichendes Interesse an der Einsicht geltend gemacht hat. Dies ist im Folgenden zu prüfen.
4.3 Die Aufsichtsbehörde hat erwogen, dass die betreffenden Verlustscheine einschliesslich der verfügten Kosten seit langem rechtskräftig seien. Sie hat dem Beschwerdeführer deshalb ein Interesse an der Einsicht abgesprochen, um anhand der Betreibungsakten nähere Informationen über die Kosten sowie Hinweise auf die "Nichtigkeit der Verlustscheine" zu erhalten. Entgegen der Auffassung der Vorinstanz hat der Beschwerdeführer (als Schuldner der Verlustscheine) damit ein genügendes schutzwürdiges Interesse zur Einsicht geltend gemacht. Es ist grundsätzlich nicht Sache der Behörden, anstelle des Betroffenen über die Erfolgschancen und den von ihm einzuschlagenden Weg zu befinden und die Akteneinsicht davon abhängig zu machen (<ref-ruling> E. 3.2.2 S. 45). Die Aufsichtsbehörde hat dem Beschwerdeführer die Akteneinsicht zu Unrecht verweigert.
4.4 An diesem Ergebnis vermag der Hinweis der Vorinstanz, der Beschwerdeführer habe nicht vor dem Betreibungsamt, sondern erst im Beschwerdeverfahren Einsicht in das Betreibungsbuch verlangt, nichts zu ändern. Das Schreiben des Beschwerdeführers vom 24. Februar 2011 an das Betreibungsamt kann in guten Treuen (vgl. <ref-ruling> E. 2c S. 154) ohne Weiteres dahingehend verstanden werden, dass er nicht nur die Betreibungsakten, sondern auch die Einträge der betreffenden Betreibungen im Betreibungsbuch einsehen will.
5. Nach dem Dargelegten ist die Beschwerde begründet, was zur Aufhebung des angefochtenen Urteils führt. In der Sache ist das Betreibungsamt anzuweisen, dem Beschwerdeführer Einsicht in die Betreibungsakten und -bücher der mit den Verlustscheinen erledigten Betreibungen zu gewähren.
Für das bundesgerichtliche Verfahren werden keine Kosten erhoben (<ref-law>). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege ist infolge Gegenstandslosigkeit abzuschreiben. Eine Parteientschädigung an den nicht anwaltlich vertretenen Beschwerdeführer ist nicht geschuldet, da ihm keine ersatzpflichtigen Kosten entstanden sind (Art. 68 Abs. 1 und 2 BGG; Art. 1 lit. a und b des Reglementes über Parteientschädigung, SR 173.110.210.3; <ref-ruling> E. 4 S. 446). Der Antrag auf Zusprechung von Genugtuung ist mangels gesetzlicher Grundlage unzulässig.

Demnach erkennt das Bundesgericht:
1. Auf das Ausstandsbegehren ist, soweit es nicht als gegenstandslos abzuschreiben ist, nicht einzutreten.
2. 2.1 Die Beschwerde in Zivilsachen wird gutgeheissen, soweit darauf einzutreten ist, und das Urteil der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn vom 14. April 2011 wird aufgehoben.
2.2 Das Betreibungsamt Olten-Gösgen wird angewiesen, dem Beschwerdeführer Einsicht in die Betreibungsakten und -bücher der mit Verlustscheinen vom 31. Mai 2000 (VS-Nr. 52699), 27. September 2002 (VS-Nr. 75187), 5. Juni 2003 (VS-Nr. 82290) und 27. November 2007 (VS-Nr. 122'468) erledigten Betreibungen zu gewähren.
3. Es werden keine Gerichtskosten erhoben.
4. Es wird keine Parteientschädigung zugesprochen.
5. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege ist infolge Gegenstandslosigkeit abzuschreiben.
6. Dieses Urteil wird den Verfahrensbeteiligten und der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 14. November 2011
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Levante