Sachverhalt:
A. Am 17. September 2009 reichte die Y._ AG beim Betreibungsamt Altstätten ein Betreibungsbegehren gegen X._ ein. In der Folge forderte das Betreibungsamt X._ telefonisch zur Abholung des Zahlungsbefehls auf. Am 5. Oktober 2009 erschien X._ auf dem Betreibungsamt und teilte mit, dass er den Zahlungsbefehl nicht entgegennehmen werde. Am 7. Oktober 2009 erhob er Beschwerde mit der Begründung, es liege kein gültiger Betreibungsort vor. Mit Entscheid vom 16. November 2009 wies der Einzelrichter des Kreisgerichts Rheintal als untere Aufsichtsbehörde für das Betreibungswesen die Beschwerde ab.
B. Gegen den Entscheid der unteren Aufsichtsbehörde gelangte X._ an das Kantonsgericht St. Gallen als obere kantonale Aufsichtsbehörde für Schuldbetreibung und Konkurs. Die obere kantonale Aufsichtsbehörde trat auf die Beschwerde wegen Fristversäumnis mit Entscheid vom 15. Dezember 2009 nicht ein.
C. Mit Eingabe vom 31. Dezember 2009 (Postaufgabe) führt X._ Beschwerde in Zivilsachen. Der Beschwerdeführer beantragt dem Bundesgericht, den Nichteintretensentscheid der oberen kantonalen Aufsichtsbehörde aufzuheben. Weiter ersucht er um aufschiebende Wirkung.
Mit Präsidialverfügung vom 4. Februar 2010 wurde der Beschwerde aufschiebende Wirkung zuerkannt. Die obere kantonale Aufsichtsbehörde hat auf eine Stellungnahme verzichtet. Die Y._ AG als Beschwerdegegnerin beantragt das Nichteintreten auf die Beschwerde. Das Betreibungsamt schliesst sinngemäss auf Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Entscheide in Schuldbetreibungs- und Konkurssachen unterliegen der Beschwerde in Zivilsachen (<ref-law>). Der Entscheid der oberen kantonalen Aufsichtsbehörde, mit welchem wegen Fristversäumnis auf die Beschwerde (<ref-law>) betreffend den Erlass eines Zahlungsbefehls nicht eingetreten wurde, stellt einen Endentscheid im Sinne von <ref-law> dar (<ref-ruling> E. 1.2 S. 351). Die Beschwerde in Zivilsachen ist unabhängig des Streitwertes (<ref-law>) zulässig.
1.2 Mit Beschwerde kann die Verletzung von u.a. Bundesrecht gerügt werden (<ref-law>). In der Beschwerdebegründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>).
2. Die obere Aufsichtsbehörde hat zur Begründung des Nichteintretensentscheides festgehalten, dass der erstinstanzliche Entscheid am 16. November 2009 als Einschreiben (Gerichtsurkunde) bei der Post aufgegeben, am 18. November 2009 dem Beschwerdeführer avisiert und von diesem am 26. November 2009 in Empfang genommen worden sei. Die Abholfrist von sieben Tagen habe am 18. November 2009 zu laufen begonnen und am 24. November 2009 geendet. Die zehntägige Rechtsmittelfrist habe demnach vom 25. November bis 4. Dezember 2009 gedauert. Der Beschwerdeführer habe mit seiner am 7. Dezember 2009 der Post übergebenen Eingabe die Rechtsmittelfrist nicht gewahrt.
Der Beschwerdeführer macht demgegenüber geltend, die Abholfrist habe erst am 25. November 2009 geendet. Die Beschwerdefrist habe am 26. November 2009 zu laufen begonnen, sodass seine Eingabe an die Vorinstanz rechtzeitig sei und der Nichteintretensentscheid gegen Bundesrecht verstosse.
3. Der Entscheid der unteren kantonalen Aufsichtsbehörde kann innert zehn Tagen nach der Eröffnung an die obere kantonale Aufsichtsbehörde weitergezogen werden (<ref-law>; vgl. aArt. 19 Abs. 1 SchKG). Anlass zur Beschwerde in Zivilsachen gibt die Bestimmung des Zeitpunktes, an welchem der erstinstanzliche Entscheid rechtswirksam eröffnet worden ist. Aus dem angefochtenen Entscheid geht hervor, dass die Post den erstinstanzlichen Entscheid dem Beschwerdeführer am 18. November 2009 avisiert hat, indem - worauf die Vorinstanz hinweist - eine Abholungseinladung in das Postfach des Empfängers gelegt wurde.
3.1 Nach der Rechtsprechung gilt (auch im Schuldbetreibungs- und Konkursverfahren; <ref-ruling> E. 1 S. 493) eine eingeschriebene Sendung - unabhängig von der konkreten durch die Post gewährten Abholfrist - immer sieben Tage nach dem erfolglosen Zustellversuch als zugestellt (<ref-ruling> E. 2b S. 35; vgl. entsprechend <ref-law>). Die Voraussetzung zum Eintritt der Zustellfiktion, wonach der Beschwerdeführer mit der Zustellung eines Beschwerdeentscheides hatte rechnen müssen (vgl. <ref-ruling> E. 2a/aa S. 34), steht zu Recht nicht in Frage, zumal er selber an die untere Aufsichtsbehörde gelangt ist. Weiter steht fest, dass die Post dem Beschwerdeführer am 18. November 2009 eine Abholungseinladung hinterlassen hat. Ob der Avis der Post - weil der Adressat nicht angetroffen wird - in den Briefkasten oder (wie hier) in das Postfach des Empfängers gelegt wurde, macht für das Datum des erfolglosen Zustellversuches keinen Unterschied (<ref-ruling> E. 3a S. 15; <ref-ruling> E. 1 S. 493; zuletzt: <ref-ruling> E. 4 und 5 S. 52). Bei erfolglosem Zustellversuch am 18. November 2009 hat am Folgetag (19. November 2009) die siebentägige Frist zu laufen begonnen und gilt die Sendung am siebten Tag, mithin am 25. November 2009 als zugestellt. Daran ändert nichts, dass es dem Beschwerdeführer möglich war, einen Tag später (und gemäss eigenen Angaben nach Ablauf der von der Post auf den 25. November 2009 angesetzten Abholfrist) noch möglich war, die Sendung auf der Poststelle in Empfang zu nehmen.
3.2 Die obere Aufsichtsbehörde hat die Zustellfiktion bereits am 24. November 2009 eintreten lassen und damit den Tag des erfolglosen Zustellversuches als ersten Tag der siebentägigen (Abholfrist-) Frist gezählt. Das Bundesgericht hat im Urteil 9C_657/2008 vom 9. Dezember 2008 zwar festgehalten, dass die siebentägige Frist auf diese Weise zu berechnen sei (publ. in: SJ 2009 I S. 308, E. 2.2). Mit diesem nicht amtlich publizierten Urteil wurde die bisherige Praxis, wie sie in <ref-ruling> ff. dargelegt wurde und auf welche sich auch die Vorinstanz beruft, nicht geändert. Aus dem nachfolgend ergangenen <ref-ruling> E. 5 S. 52 geht klar hervor, dass die Zustellfiktion am siebten Tag nach dem ersten erfolglosen Zustellversuch eintritt.
3.3 Somit begann die zehntägige Beschwerdefrist für die Weiterziehung des Entscheides der unteren Aufsichtsbehörde an die obere kantonale Instanz mit rechtswirksamer Eröffnung am 25. November 2009 (d.h. am siebten Tag nach erfolglosem Zustellversuch vom 18. November 2009, vgl. E. 3.1) mit dem 26. November 2009 zu laufen (Art. 18 Abs. 1, Art. 31 Abs. 1 SchKG) und endigte am 5. Dezember 2009, verlängerte sich aber, weil dieser Tag ein Samstag war, auf den nächstfolgenden Werktag, den 7. Dezember 2009 (<ref-law>). Mit der an diesem Tag der schweizerischen Post (<ref-law>) übergebenen Eingabe hat der Beschwerdeführer die Beschwerdefrist gewahrt, und die Beschwerde an die obere kantonale Aufsichtsbehörde erweist sich rechtzeitig. Die Rüge des Beschwerdeführers, durch den angefochtenen Nichteintretensentscheid sei Bundesrecht verletzt worden, ist begründet.
4. Aus diesen Gründen ist die Beschwerde in Zivilsachen gutzuheissen. Der Entscheid der oberen kantonalen Aufsichtsbehörde ist aufzuheben mit der Folge, dass die Vorinstanz die Beschwerde des Beschwerdeführers als rechtzeitig zu behandeln hat.
Auf die Erhebung von Gerichtskosten wird verzichtet (<ref-law>). Eine Parteientschädigung ist dem nicht anwaltlich vertretenen Beschwerdeführer nicht zuzusprechen (vgl. <ref-law>; Art. 1 des Reglementes über die Parteientschädigung; SR 173.110.210.3).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird gutgeheissen und der Entscheid des Kantonsgerichts St. Gallen als oberer kantonaler Aufsichtsbehörde für Schuldbetreibung und Konkurs vom 15. Dezember 2009 wird aufgehoben.
2. Es werden keine Gerichtskosten erhoben.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien, dem Betreibungsamt Altstätten und dem Kantonsgericht St. Gallen als oberer kantonaler Aufsichtsbehörde für Schuldbetreibung und Konkurs schriftlich mitgeteilt.
Lausanne, 17. März 2010
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Escher Levante