Sachverhalt:
A. Am 22. April 2009 reichte Y._ beim Betreibungsamt St. Gallen ein Betreibungsbegehren für den Betrag von Fr. 554'014.55 (nebst Zins) gegen X._ ein. Eine Mitarbeitende des Betreibungsamtes stellte den Zahlungsbefehl in der Folge an der Adresse von X._ in Z._ zu. Dagegen erhob dieser Rechtsvorschlag. Gestützt auf den definitiven Rechtsöffnungsentscheid des Kreisgerichts St. Gallen stellte Y._ am 10. Dezember 2009 das Fortsetzungsbegehren. Das Betreibungsamt kündigte X._ daraufhin mit Schreiben vom 11. Dezember 2009 die Pfändung an.
B. Mit Eingabe an das Betreibungsamt vom 17. Dezember 2009 machte X._ geltend, er halte sich überwiegend in Deutschland auf, weshalb ihm die Pfändung zu kurzfristig angekündigt worden sei. In künftigen Verfügungen sei ihm deshalb eine angemessene Frist anzusetzen. Im Übrigen sei vor dem Kantonsgericht eine Feststellungsklage hängig, weshalb das Pfändungsverfahren auszusetzen sei.
Daraufhin gewährte ihm das Betreibungsamt eine längere Frist und lud ihn mit Schreiben vom 18. Dezember 2009 unter Straffolge vor, am 8. Januar 2010 auf dem Betreibungsamt zwecks Abklärung seiner Vermögensverhältnisse zu erscheinen. Dagegen erhob X._ am 2. Januar 2010 Beschwerde und machte geltend, sein Wohnsitz befinde sich in Deutschland.
C. Am 16. Februar 2010 wies das Kreisgericht St. Gallen als untere Aufsichtsbehörde für Schuldbetreibung die Beschwerde ebenso ab wie das Kantonsgericht St. Gallen als obere Aufsichtsbehörde für Schuldbetreibung am 25. März 2010 (rechtshilfeweise Zustellung in Deutschland am 18. Mai 2010).
D. Dem Bundesgericht beantragt X._ (nachfolgend Beschwerdeführer) in seiner Beschwerde vom 25. Mai 2010 die Aufhebung des kantonsgerichtlichen Entscheides und sinngemäss die Aufhebung des Betreibungsverfahrens. Zudem ersucht er um aufschiebende Wirkung.
Das Betreibungsamt schliesst auf Abweisung des Gesuchs um aufschiebende Wirkung. Das Kantonsgericht sowie Y._ (nachfolgend Beschwerdegegner) haben sich dazu nicht vernehmen lassen. Mit Verfügung vom 28. Juli 2010 hat die Abteilungspräsidentin der Beschwerde die aufschiebende Wirkung zuerkannt.
Es sind die Akten, in der Sache aber keine Vernehmlassungen eingeholt worden. Auf entsprechende Aufforderung hin bezeichnete der Beschwerdeführer als Zustelldomizil seine Adresse in Z._.
Mit Eingaben vom 19. Juli 2010 und 1. September 2010 hat er seine Beschwerde ergänzt. Soweit er im letztgenanntem Schreiben beantragt, es sei das Betreibungsverfahren sowie ein damit zusammenhängendes Strafverfahren einzustellen, ist der Instruktionsrichter darauf mit Verfügung vom 3. September 2010 nicht eingetreten.

Erwägungen:
1. 1.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>; <ref-ruling> E. 1.1 S. 401). Der angefochtene Entscheid stammt von der letzten kantonalen Instanz (<ref-law>) und stellt einen Endentscheid dar (<ref-law>; <ref-ruling> E. 1.2 S. 189).
1.2 Der Beschwerdeführer hat seine ergänzenden Eingaben vom 19. Juli 2007 und 1. September 2010 erst nach Ablauf der Rechtsmittelfrist von 10 Tagen eingereicht (<ref-law>; vgl. auch <ref-ruling> E. 2.2 S. 21). Darauf ist nicht einzutreten.
1.3 Vor Bundesgericht dürfen keine neuen Tatsachen und Beweismittel vorgebracht werden, es sei denn, erst der Entscheid der Vorinstanz habe dazu Anlass gegeben (<ref-law>). Der Beschwerdeführer äussert sich erstmals detailliert vor Bundesgericht darüber, in welchem Zeitraum er in der Schweiz gearbeitet und wie sich seine damalige Wohn- und Familiensituation genau präsentiert habe. Zudem bringt er erstmals vor, sein Lebensmittelpunkt habe sich gar nie in der Schweiz befunden (Ziff. 2 und Ziff. 7 Abs. 2 der Beschwerde). Diese neuen Tatsachenvorbringen können nicht berücksichtigt werden, da der Beschwerdeführer Grund und Gelegenheit gehabt hätte, sie bereits vor dem Kantonsgericht vorzubringen (<ref-ruling> E. 4.4.3 S. 128 f.). Die als Beweismittel neu eingereichte E-Mail des Einwohneramtes Z._ vom 3. Mai 2010 ist nach dem angefochtenen Entscheid entstanden (<ref-ruling> E. 5.2.4 S. 229 f. mit Hinweisen). Diese Tatsachen und Beweismittel sind unzulässig und nicht zu berücksichtigen.
2. 2.1 Gemäss <ref-law> ist der Schuldner an seinem Wohnsitz zu betreiben. Das Betreibungsrecht knüpft hierbei an das Zivilrecht an (<ref-law>; in internationalen Verhältnissen <ref-law>, vgl. dazu: <ref-ruling> E. 2a S. 8). Demnach befindet sich der Wohnsitz dort, wo sich der Schuldner mit der Absicht dauernden Verbleibens aufhält.
2.2 Nach Eingang eines Betreibungsbegehrens ist es nicht Aufgabe des Betreibungsamtes, den Wohnsitz des Schuldners ausfindig zu machen. Es muss hingegen die Angaben des Gläubigers überprüfen, da die Zuständigkeit davon abhängt. Behauptet der Schuldner, er habe einen von den Angaben des Gläubigers abweichenden Wohnsitz, so ist er hiefür beweispflichtig (SCHMID, in: Basler Kommentar, 1998, N. 51 zu <ref-law>; vgl. auch <ref-ruling> E. 1b S. 112).
3. 3.1 Die Beschwerde ist zu begründen (<ref-law>). Mit ihr ist in gedrängter Form durch Auseinandersetzung mit den Erwägungen des angefochtenen Entscheids darzulegen, welche Vorschriften und warum sie von der Vorinstanz verletzt worden sein sollen. Allgemein gehaltene Einwände, die ohne aufgezeigten oder erkennbaren Zusammenhang mit bestimmten Entscheidungsgründen vorgebracht werden, genügen nicht (<ref-ruling> E. 3.3 S. 60).
3.2 Wird eine Tatsachenfeststellung beanstandet, muss in der Beschwerdeschrift dargelegt werden, inwiefern diese willkürlich (<ref-ruling> E. 1.5 S. 401) oder durch eine andere Rechtsverletzung im Sinne von <ref-law> (z.B. <ref-law> oder <ref-law>) zustande gekommen ist und inwiefern die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Auf rein appellatorische Kritik am Sachverhalt tritt das Bundesgericht nicht ein (<ref-ruling> E. 5.2.2 S. 322; <ref-ruling> E. 2.2 S. 41).
3.3 Das Kantonsgericht hielt fest, der Beschwerdeführer sei seit dem 1. Juli 2007 in Z._ ordentlich angemeldet. Er sei zudem als Gesellschafter und Geschäftsführer einer GmbH tätig, wobei im entsprechenden Handelsregisterauszug ebenfalls Z._ als Wohnort angegeben werde. Der Beschwerdeführer bestreite zudem nicht, in Z._ seinen Wohnsitz begründet zu haben.
Im ganzen Verfahren habe er keine Nachweise (wie insbesondere eine Abmeldung) vorgelegt, woraus ersichtlich wäre, dass er seinen Wohnsitz zwischenzeitlich nach Deutschland verlegt habe. Mit blossen Behauptungen werde er seiner Beweisführungslast nicht gerecht. Sei damit nicht bewiesen, dass sein Lebensmittelpunkt und damit Wohnsitz neu in Deutschland liege, erweise sich die Beschwerde als unbegründet.
3.4 Der Beschwerdeführer unterlässt es, sich mit dieser massgeblichen Erwägung des Kantonsgerichts substanziiert auseinanderzusetzen.
Er führt dazu einzig aus, dieser Nachweis der Wohnsitzverlegung sei gar nicht erforderlich, da er seinen Lebensmittelpunkt gar nie nach Z._ verlegt habe. Damit wendet er sich gegen die kantonsgerichtliche Tatsachenfeststellung. Soweit er sich dazu auf neue Tatsachen beruft, ist dies wie erwähnt unzulässig (vgl. E. 1.3 oben). Inwiefern die kantonsgerichtliche Feststellung, er habe in Z._ gelebt, dort seinen Lebensmittelpunkt begründet und zudem die dortige Wohnsitzbegründung in seiner Beschwerde an das Kantonsgericht ausdrücklich anerkannt, sich im Übrigen als willkürlich erweisen soll, legt der Beschwerdeführer nicht dar und ist auch nicht ersichtlich. Tatsächlich hat der Beschwerdeführer vor Kantonsgericht selber ausgeführt, er habe in Z._ gelebt und dort einen Wohnsitz begründet. Vor Bundesgericht begnügt er sich einzig damit, den Sachverhalt und vor allem die Wohnsituation aus seiner geänderten Sichtweise darzulegen. Damit wird er seinen Begründungsanforderungen nicht gerecht.
4. Aus den dargelegten Gründen ist auf die Beschwerde nicht einzutreten. Damit trägt der Beschwerdeführer die Kosten des Verfahrens (<ref-law>). Eine Parteientschädigung an den Beschwerdegegner entfällt, da er sich zum Gesuch um aufschiebende Wirkung von vornherein nicht hat vernehmen lassen und in der Sache keine Vernehmlassung eingeholt wurde (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien, dem Betreibungsamt St. Gallen und dem Kantonsgericht St. Gallen, obere kantonale Aufsichtsbehörde für Schuldbetreibung und Konkurs, schriftlich mitgeteilt.
Lausanne, 8. September 2010
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Bettler