Sachverhalt:
A. In den beiden von der B._ GmbH für eine Forderung von jeweils Fr. 165'388.-- eingeleiteten Betreibungen Nrn. 1 und 2 stellte das Betreibungsamt C._ A._ am 1. Mai 2009 die Zahlungsbefehle zu. A._ schlug in beiden Fällen Recht vor. Die B._ GmbH sah davon ab, eine Beseitigung der Rechtsvorschläge anzustreben, und leistete der vom Betriebenen in der Betreibung Nr. 1 verlangten Aufforderung des Betreibungsamtes, die Beweismittel für ihre Forderung einzureichen (<ref-law>), keine Folge.
B. Mit Eingabe vom 16. Juli 2009 stellte A._ bei der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn das Gesuch, die Betreibungen Nrn. 1 und 2 des Betreibungsamtes C._ zu löschen, da sie missbräuchlich seien und jeglicher Beweisgrundlagen entbehrten. Die kantonale Aufsichtsbehörde behandelte die Eingabe als Beschwerde gegen die Zahlungsbefehle, die auf rechtsmissbräuchlichen und damit nichtigen Betreibungsbegehren beruhten, und wies sie am 7. September 2009 ab.
C. A._ verlangt mit Beschwerde vom 17. September 2009 an das Bundesgericht, das Urteil der kantonalen Aufsichtsbehörde vom 7. September 2009 aufzuheben, festzustellen, dass die Betreibungen Nrn. 1 und 2 des Betreibungsamtes C._ nichtig seien, und dieses Amt anzuweisen, die beiden Betreibungen zu löschen. Mit Eingaben vom 14. Oktober 2009 und vom 6. November 2009 teilt er ausserdem mit, dass das Betreibungsamt C._ am 13. Oktober 2009 in einer weiteren durch die B._ GmbH gegen ihn persönlich eingeleiteten Betreibung (Nr. 3) den vom 12. Oktober 2009 datierten Zahlungsbefehl über Fr. 175'388.-- bzw. das Betreibungsamt E._ in der von der gleichen Betreibungsgläubigerin gegen die D._ AG, deren Inhaber er sei, eingeleiteten Betreibung Nr. 4 am 6. November 2009 den von diesem Tag datierten Zahlungsbefehl über den gleichen Betrag zugestellt habe.
Vernehmlassungen zur Beschwerde sind nicht eingeholt worden.

Erwägungen:
1. Entscheide der kantonalen Aufsichtsbehörden in Schuldbetreibungs- und Konkurssachen unterliegen unabhängig von einem allfälligen Streitwert der Beschwerde in Zivilsachen (Art. 72 Abs. 2 lit. a und Art. 74 Abs. 2 lit. c BGG). Der angefochtene Entscheid stammt von der letzten kantonalen Instanz (<ref-law>) und befindet über die Gültigkeit von Zahlungsbefehlen, d.h. über betreibungsamtliche Verfügungen nach <ref-law>, so dass er einen Endentscheid im Sinne von <ref-law> darstellt (<ref-ruling> E. 1.2 S. 351).
Den angefochtenen Entscheid nahm der Beschwerdeführer am 10. September 2009 in Empfang. Der letzte Tag der hier geltenden Frist von zehn Tagen (<ref-law>), der 20. September 2009, fiel auf einen Sonntag, so dass die Beschwerde spätestens am 21. September 2009 (Montag) zur Post zu bringen war. Auf die Beschwerdeeingabe vom 17. September 2009 ist mithin ohne weiteres einzutreten. Hingegen sind die erst am 14. Oktober 2009 bzw. am 6. November 2009 aufgegebenen Ergänzungen, mit denen ohnehin erst nach Fällung des angefochtenen Entscheids eingetretene Tatsachen vorgebracht werden, unbeachtlich.
2. Die kantonale Aufsichtsbehörde verweist auf <ref-law>, wonach das Betreibungsamt Dritten von einer Betreibung keine Kenntnis gibt, wenn sie nichtig (oder aufgrund einer Beschwerde oder eines Urteils aufgehoben worden) ist. Nichtig seien nach <ref-law> Verfügungen, die gegen Vorschriften verstiessen, die im öffentlichen Interesse oder im Interesse von am Verfahren nicht beteiligten Personen erlassen worden seien. Dazu gehöre auch das Rechtsmissbrauchsverbot nach <ref-law>, das in der gesamten Rechtsordnung, insbesondere auch im Schuldbetreibungsrecht, Anwendung finde.
Zu den beiden hier in Frage stehenden Betreibungen hält die Vorinstanz fest, aus der Stellungnahme der Beschwerdegegnerin zum Löschungsbegehren gehe nicht hervor, worauf die Betreibungsforderungen genau beruhten. Im Wesentlichen würden ausstehende Lohnzahlungen angeführt. In den Betreibungsbegehren würden als Gründe der Betreibungen nicht ausbezahlte Arbeiten, Nichtbezahlen von Sozialbeiträgen, Kundenverluste, Umtriebe und die Missachtung von Abmachungen erwähnt. Es würden keine Einzelheiten, keine Zusammensetzung und keine Berechnung der Forderungen offengelegt, so dass es sich um eine pauschale Umschreibung von Anspruchsgrundlagen handle. Ferner deute zur Zeit nichts darauf hin, dass die Beschwerdegegnerin die vom Beschwerdeführer erhobenen Rechtsvorschläge beseitigen zu lassen gedenke.
In Würdigung der von ihr festgehaltenen Gegebenheiten hält die kantonale Aufsichtsbehörde dafür, dass das Vorliegen eines Rechtsmissbrauchs nicht angenommen werden könne. Auch wenn die Beschwerdegegnerin der Aufforderung des Betreibungsamtes, Beweismittel für die den Betreibungen zugrunde liegende Forderung einzureichen, nicht nachgekommen sei, sei nicht auszuschliessen, dass den Betreibungen eine bestehende Forderung zugrunde liege. Gerade im Wirtschaftsleben komme es häufig vor, dass trotz des Bestehens einer Forderung keine sie bestätigenden Urkunden vorlägen. Es könne angesichts der Besonderheit des schweizerischen Vollstreckungsrechts, wonach eine Betreibung auch dann eingeleitet werden könne, wenn der Gläubiger nicht konkret darlegen könne, was für eine Forderung ihr zugrunde liege und aus was für Kontakten mit dem Betriebenen diese entstanden sein soll, nicht angenommen werden, die Beschwerdegegnerin glaube nicht an die Durchsetzbarkeit ihrer Forderung auf dem Betreibungsweg. Ausserdem sei zu beachten, dass Betreibungen häufig auch bloss zum Zweck der Verjährungsunterbrechung eingeleitet würden, um dem drohenden Untergang der Forderung zu entgehen. Die Tatsache, dass zunächst beim Betreibungsamt C._ zwei identische Betreibungen und kurze Zeit später beim Betreibungsamt E._ eine Betreibung über den gleichen Betrag und mit gleicher Forderungsbegründung eingeleitet worden seien, spreche noch nicht für das Vorliegen eines Rechtsmissbrauchs, zumal die in E._ eingeleitete Betreibung nicht gegen den Beschwerdeführer persönlich, sondern gegen die von ihm geführte D._ AG gerichtet gewesen sei und die Beschwerdegegnerin als Betreibungsgläubigerin das Risiko trage, den richtigen Schuldner zu betreiben. Es müsse dem Betreibungsgläubiger bei Ungewissheit darüber, wer Schuldner sei, gestattet sein, für die gleiche Forderung vorsorglich mehrere mögliche Schuldner zu betreiben.
3. 3.1 Nach dem schweizerischen Vollstreckungsrecht kann ein Zahlungsbefehl grundsätzlich gegenüber jedermann erwirkt werden, ohne dass der Bestand der in Betreibung gesetzten Forderung nachzuweisen wäre (<ref-ruling> E. 2a S. 150 mit Hinweisen). Dem Betreibungsamt und den betreibungsrechtlichen Aufsichtsbehörden steht es nicht zu, über die Begründetheit der Betreibungsforderung zu befinden (<ref-ruling> E. 3b S. 21). Allerdings verdient die Partei, die sich nicht an die auch im Zwangsvollstreckungsverfahren zu beachtenden Regeln von Treu und Glauben (<ref-law>) hält, keinen Rechtsschutz (<ref-ruling> E. 2 S. 120 mit Hinweis). Eine Betreibung ist deshalb nichtig, wenn mit einem Betreibungsbegehren offensichtlich Recht missbraucht wird (<ref-law>). Rechtsmissbräuchliches Verhalten liegt vor, wenn der Betreibungsgläubiger offensichtlich Ziele verfolgt, die mit der Zwangsvollstreckung nicht das Geringste zu tun haben, es ihm beispielsweise einzig darum geht, den Betriebenen zu schikanieren und zu bedrängen.
3.2 Der Beschwerdeführer verweist hauptsächlich auf vier Betreibungen, die von der Beschwerdegegnerin im Mai 2007 für Forderungsbeträge von Fr. 28'500.-- bzw. Fr. 19'800.--, im Dezember 2008 für einen Forderungsbetrag von Fr. 104'650.-- und im Mai 2009 für einen Forderungsbetrag von (ebenfalls) Fr. 165'388.-- in E._ gegen die D._ AG, deren Inhaber er sei, eingeleitet worden seien. Durch Urteil vom 15. Juni 2009 habe die Aufsichtsbehörde über das Betreibungsamt E._ diese Betreibungen als nichtig erklärt. Auf eine von der Beschwerdegegnerin gegen diesen Entscheid erhobene Beschwerde sei das Bundesgericht nicht eingetreten, so dass die Betreibungen gestützt auf die entsprechende aufsichtsbehördliche Anweisung gelöscht würden. In Anbetracht der angeführten Betreibungen seien auch die beiden im Kanton Solothurn eingeleiteten Betreibungen missbräuchlich und schikanös.
3.3 Vorab ist festzuhalten, dass sich aus dem Urteil des Bundesgerichts vom 27. August 2009 nichts zu Gunsten des Standpunkts des Beschwerdeführers ableiten lässt: Die Präsidentin der erkennenden Abteilung hat darin nicht über die Gültigkeit der von der Beschwerdegegnerin in E._ eingeleiteten Betreibungen materiell befunden, sondern (aus formeller Sicht) einzig festgehalten, dass die von der Beschwerdegegnerin gegen die Nichtigerklärung der Betreibungen erhobene Beschwerde keine den gesetzlichen Anforderungen genügende Begründung enthalte und daher auf sie nicht einzutreten sei. Die Betreibungen waren zudem gegen die D._ AG, d.h. gegen ein Rechtssubjekt gerichtet, dessen Inhaber der Beschwerdeführer nach seinen Angaben zwar ist, das jedoch von seiner Person zu unterscheiden ist. Das Argument der Vorinstanz, einem Gläubiger müsse freistehen, für die gleiche Forderung gegen verschiedene Rechtssubjekte Betreibungen einzuleiten, falls nicht klar sei, wer den geforderten Betrag schulde, ist nicht zu beanstanden, und der Beschwerdeführer vermag ihm denn auch nichts entgegenzuhalten.
Zu den beiden hier zu beurteilenden Betreibungen Nrn. 1 und 2 des Betreibungsamtes C._ erklärt der Beschwerdeführer selbst, dass die eine gegen ihn persönlich und die andere gegen seine Einzelfirma (F._) gerichtet seien. Von einer eigentlichen Wiederholung der gleichen Betreibung, worin unter gewissen Umständen ein Indiz für ein rechtsmissbräuchliches Verhalten der Beschwerdegegnerin erblickt werden könnte, kann bei den dargelegten Gegebenheiten auch bei einer Mitberücksichtigung der in E._ eingeleiteten Betreibungen nicht gesprochen werden.
4. Die Beschwerde ist nach dem Gesagten abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Da keine Vernehmlassungen zur Beschwerde eingeholt worden und der Beschwerdegegnerin somit keine Kosten erwachsen sind, entfällt die Zusprechung einer Parteientschädigung.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien, dem Betreibungsamt C._ und der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 26. November 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Gysel