Sachverhalt:
A. Mit Entscheid vom 2. März 2007 sprach das Kreisgericht Rheintal X._ der mehrfachen qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz (<ref-law>) und der mehrfachen Widerhandlung gegen das Bundesgesetz über Aufenthalt und Niederlassung der Ausländer (Art. 23 Abs. 2 ANAG) schuldig und bestrafte ihn mit einer Freiheitsstrafe von 41⁄2 Jahren (unter Anrechnung der Untersuchungshaft von 118 Tagen).
Die von X._ erhobene Berufung wies das Kantonsgericht St. Gallen mit Entscheid vom 12. Februar 2009 ab.
B. X._ führt Beschwerde in Strafsachen mit den Anträgen, das Urteil des Kantonsgerichts St. Gallen vom 12. Februar 2009 sei aufzuheben, und die Sache sei zur Neubeurteilung an die Vorinstanz zurückzuweisen.

Erwägungen:
1. 1.1 Den Verurteilungen des Beschwerdeführers liegt der folgende Sachverhalt zugrunde (angefochtenes Urteil S. 2 f.):
Am Sonntag, den 14. März 2004, wurde am Zollamt St. Margrethen ein Car durch die Grenzwache angehalten und kontrolliert. Dabei wurden in konstruktionsbedingten Stauräumen drei Personen festgestellt, welche nicht über gültige Einreisepapiere verfügten. Eine vierte Person ohne gültige Einreisedokumente befand sich an Bord des Cars. Anlässlich einer weitergehenden Kontrolle wurden insgesamt 6,868 Kilogramm Heroingemisch aufgespürt. Dieses befand sich in Konservendosen eingeschweisst in einer Reisetasche im Gepäckraum (rund sechs Kilogramm) sowie in der Mittelkonsole neben dem Führersitz versteckt (rund ein Kilogramm). Der Beschwerdeführer war die verantwortliche Person im Car (Reiseunternehmer). Im Wissen um die fehlenden Einreisevoraussetzungen hatte er die betroffenen Personen heimlich in die Schweiz gebracht sowie die Betäubungsmittel wissentlich eingeführt. Weitere Abklärungen ergaben, dass der mutmassliche Abnehmer der entdeckten Drogenlieferung bereits am 19. Februar 2004 rund drei Kilogramm Heroingemisch empfangen hatte, welches auf dem gleichen Transportweg in die Schweiz gelangt war.
1.2 Vom Beschwerdeführer nicht angefochten ist der Schuldspruch wegen mehrfacher Widerhandlung gegen das Bundesgesetz über Aufenthalt und Niederlassung der Ausländer. Verfahrensgegenstand bildet mithin einzig die Verurteilung wegen mehrfacher qualifizierter Widerhandlung gegen das BetmG.
2. 2.1 Der Beschwerdeführer rügt eine willkürliche Beweiswürdigung und als Folge daraus eine offensichtlich unrichtige Sachverhaltsfeststellung. Im Ergebnis verletze das angefochtene Urteil den aus der Unschuldsvermutung abgeleiteten Grundsatz "in dubio pro reo". Es handle sich vorliegend um einen reinen Indizienprozess, werde doch seine Verurteilung einzig auf die Auswertung von Protokollen von Telefonkontrollen abgestützt. Bei einer korrekten Würdigung dieser Beweise bestünden nicht zu unterdrückende Zweifel an seiner Schuld.
2.2 <ref-law> gewährleistet den Anspruch darauf, von den staatlichen Organen ohne Willkür behandelt zu werden. Auf dem Gebiet der Beweiswürdigung ist die Kognition des Bundesgerichts auf Willkür beschränkt. Willkür in der Beweiswürdigung liegt vor, wenn die Behörde in ihrem Entscheid von Tatsachen ausgeht, die mit der tatsächlichen Situation in klarem Widerspruch stehen oder auf einem offenkundigen Fehler beruhen (<ref-ruling> E. 5.4). Dass das angefochtene Urteil mit der Darstellung des Beschwerdeführers nicht übereinstimmt oder eine andere Lösung oder Würdigung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, genügt praxisgemäss für die Begründung von Willkür nicht (<ref-ruling> nicht publ. E. 4.1; <ref-ruling> E. 2b).
Gemäss der in <ref-law> und Art. 6 Ziff. 1 EMRK verankerten Maxime "in dubio pro reo" ist bis zum gesetzlichen Nachweis der Schuld zu vermuten, dass die einer strafbaren Handlung angeklagte Person unschuldig ist (<ref-ruling> E. 4; <ref-ruling> E. 2 mit Hinweisen). Als Beweiswürdigungsregel besagt die Maxime, dass sich das Strafgericht nicht von der Existenz eines für die beschuldigte Person ungünstigen Sachverhalts überzeugt erklären darf, wenn bei objektiver Betrachtung erhebliche und nicht zu unterdrückende Zweifel bestehen, dass sich der Sachverhalt so verwirklicht hat. Inwiefern dieser Grundsatz verletzt sein soll, prüft das Bundesgericht nur unter dem Gesichtspunkt der Willkür, das heisst, es greift nur ein, wenn das Sachgericht die beschuldigte Person verurteilte, obgleich bei objektiver Würdigung des Beweisergebnisses offensichtlich erhebliche bzw. schlechterdings nicht zu unterdrückende Zweifel an deren Schuld fortbestehen. Bloss abstrakte und theoretische Zweifel sind nicht massgebend, weil solche immer möglich sind und absolute Gewissheit nicht verlangt werden kann (BGE <ref-ruling> E. 2 und 4; <ref-ruling> E. 2; Urteil des Bundesgerichts 6B_923/2008 vom 2. Februar 2009 E. 2).
Wird eine willkürliche Beweiswürdigung gerügt, reicht es nicht aus, wenn der Beschwerdeführer zum Beweisergebnis frei plädiert und darlegt, wie seiner Auffassung nach die vorhandenen Beweise richtigerweise zu würdigen gewesen wären, wie er dies in einem appellatorischen Verfahren mit freier Rechts- und Tatsachenüberprüfung tun könnte. Er muss gemäss ständiger Rechtsprechung vielmehr aufzeigen, inwiefern die angefochtene Beweiswürdigung die Verfassung dadurch verletzen sollte, dass sie im Ergebnis offensichtlich unhaltbar wäre (vgl. <ref-ruling> E. 4; <ref-ruling> E. 2; <ref-ruling> E. 3c).
2.3 Dabei können auch indirekte, mittelbare Beweise, sog. Anzeichen oder Indizien, einen für die Beweisführung bedeutsamen Schluss erlauben. Indizien sind Tatsachen, die einen Schluss auf eine andere, unmittelbar erhebliche Tatsache zulassen. Beim Indizienbeweis wird vermutet, dass eine nicht bewiesene Tatsache gegeben ist, weil sich diese Schlussfolgerung aus bewiesenen Tatsachen (Indizien) nach der Lebenserfahrung aufdrängt. Der Indizienbeweis ist dem direkten Beweis gleichwertig (Robert Hauser/Erhard Schweri/Karl Hartmann, Schweizerisches Strafprozessrecht, 6. Auflage, 2005, § 59 Rz. 14). Da ein Indiz jedoch immer nur mit einer gewissen Wahrscheinlichkeit auf die Täterschaft oder die Tat hinweist, lässt es, einzeln betrachtet, die Möglichkeit des Andersseins offen, enthält daher auch den Zweifel (Hans Walder, Der Indizienbeweis im Strafprozess, ZStrR 108/1991, S. 309; derselbe, Die Beweisführung in Strafsachen, insbesondere der Indizienbeweis, 1974/75, S. 49). Es ist jedoch zulässig, aus der Gesamtheit der verschiedenen Indizien, welche je für sich allein betrachtet nur mit einer gewissen Wahrscheinlichkeit auf eine bestimmte Tatsache oder Täterschaft hindeuten und insofern Zweifel offen lassen, auf den vollen rechsgenügenden Beweis von Tat oder Täter zu schliessen (Hauser/Schweri/Hartmann, a.a.O., § 59 Rz. 15).
2.4 Die Vorinstanz hat erwogen, als Beweismittel lägen ausschliesslich Protokolle von Telefonkontrollen vor. Telefongesprächen zwischen einer Person namens "P._" in Serbien und zwei Personen in der Schweiz - Q._ und R._ - sei zu entnehmen, dass der Fahrer, welcher den "Golf III" am 19. Februar 2004 überreicht habe, am 14. März 2004 auch den "Golf VI" übergebe. Dass es sich bei dem erwähnten Liefergegenstand "Golf VI" um sechs Kilogramm Heroingemisch handle, ergebe sich aus der Umschreibung der Verpackung des "Golf VI" mit Salat- und Bohnenkonserven und den damit übereinstimmenden, anlässlich der Grenzkontrolle sichergestellten Konservendosen, in welchen sich das Heroingemisch befunden habe. Demzufolge spreche einiges dafür, dass der Ausdruck "Golf III" drei Kilogramm Heroingemisch bezeichne.
Aus den Gesprächsprotokollen folge weiter, dass der Fahrer und Lieferant des "Golfs III" und des "Golfs VI" geschlagen worden sei. Gleichzeitig sei belegt, dass der Beschwerdeführer am 14. Februar 2004 tatsächlich in Belgrad in eine Schlägerei involviert gewesen sei. Weiter werde der "Geschlagene" auch als "S._" oder "T._" bzw. als "Buschauffeur" bezeichnet. "S._" bzw. "T._" aber sei der Spitznamen des Beschwerdeführers, was von diesem im Übrigen ausdrücklich bestätigt worden sei. Zudem sei in einem Gespräch vom "Vater des Geschlagenen" und dessen Mobiltelefonnummer die Rede, wobei sich die genannte Telefonnummer tatsächlich U._, dem Vater des Beschwerdeführers, habe zuordnen lassen. Ferner habe "P._" am 14. März 2004 mehrfach erfolglos versucht, den Beschwerdeführer auf dessen privater Mobiltelefonnummer zu erreichen.
Die Vorinstanz schliesst, es sei damit erstellt, dass alleine der Beschwerdeführer als Täter in Frage komme. Aufgrund der Protokolle der Telefongespräche habe weiter als nachgewiesen zu gelten, dass der Beschwerdeführer die Drogen nach seiner Ankunft in Zürich Q._ hätte übergeben sollen. Der Beschwerdeführer habe mithin zweifellos um den Inhalt der fraglichen Konservendosen in der Reisetasche gewusst. Anders sehe es bezüglich des in der Mittelkonsole des Reisecars aufgefundenen Heroingemischs aus. Dieses könne dem Beschwerdeführer nicht zweifelsfrei zugeordnet werden, da hierauf in den Telefongesprächen nicht unmittelbar Bezug genommen werde (vgl. zum Ganzen angefochtenes Urteil S. 4 ff.).
Die Vorinstanz schliesst, es sei damit erstellt, dass alleine der Beschwerdeführer als Täter in Frage komme. Aufgrund der Protokolle der Telefongespräche habe weiter als nachgewiesen zu gelten, dass der Beschwerdeführer die Drogen nach seiner Ankunft in Zürich Q._ hätte übergeben sollen. Der Beschwerdeführer habe mithin zweifellos um den Inhalt der fraglichen Konservendosen in der Reisetasche gewusst. Anders sehe es bezüglich des in der Mittelkonsole des Reisecars aufgefundenen Heroingemischs aus. Dieses könne dem Beschwerdeführer nicht zweifelsfrei zugeordnet werden, da hierauf in den Telefongesprächen nicht unmittelbar Bezug genommen werde (vgl. zum Ganzen angefochtenes Urteil S. 4 ff.).
2.5 2.5.1 Was der Beschwerdeführer gegen diese Beweiswürdigung der Vorinstanz vorbringt, ist nicht geeignet, Willkür respektive eine Verletzung des Grundsatzes "in dubio pro reo" darzutun. Er stellt der vorinstanzlichen Begründung über weite Strecken lediglich seine eigene Sicht der Dinge gegenüber, ohne näher zu erörtern, inwiefern der Entscheid (auch) im Ergebnis schlechterdings unhaltbar sein sollte. Seine Ausführungen erschöpfen sich damit insoweit in einer unzulässigen appellatorischen Kritik am angefochtenen Urteil und genügen den Begründungsanforderungen gemäss <ref-law> nicht.
2.5.2 Soweit auf seine Rügen überhaupt eingetreten werden kann, sind sie nicht stichhaltig. So macht er im Wesentlichen geltend, er sei das Opfer einer Verwechslung von "P._". In Tat und Wahrheit müsse es sich beim "geschlagenen Fahrer" um eine andere Person, nämlich um V._ handeln.
Die Vorinstanz hat im angefochtenen Urteil eingehend und willkürfrei begründet, dass die verschiedenen Indizien (Beteiligung des Beschwerdeführers an einer Schlägerei am 14. Februar 2004, Umschreibung des "Geschlagenen" als "S._" oder "T._" bzw. als "Buschauffeur" und Bezeichnung von U._ als Vater des Geschlagenen) für die Täterschaft des Beschwerdeführers sprechen würden. Nicht unhaltbar ist in diesem Zusammenhang insbesondere die Feststellung der Vorinstanz, es sei durchaus denkbar, dass der Schlag, welcher der Beschwerdeführer am 14. Februar 2004 erhalten und unstreitig eine Schwellung hervorgerufen habe, erst nachträglich zur Herausbildung eines Hämatoms geführt habe, welches bei der Drogenübergabe am 19. Februar 2004 (noch) zu erkennen gewesen sei. Die Vorinstanz ist ferner nicht in Willkür verfallen, indem sie hervorgehoben hat, aus dem Umstand, dass allenfalls auch V._ bei der Schlägerei vom 14. Februar 2004 in Belgrad sichtbare Gesichtsverletzungen erlitten habe, vermöge der Beschwerdeführer nichts zu seinen Gunsten abzuleiten (vgl. angefochtenes Urteil S. 5 f. sowie erstinstanzliches Urteil S. 31). Dementsprechend konnte die Vorinstanz im Ergebnis die Ausführungen des Beschwerdeführers, "P._" habe ihn mit V._ verwechselt, als blosse Schutzbehauptung werten, zumal mehrere Zeugen unabhängig voneinander angaben, der Beschwerdeführer und "P._" hätten sich persönlich gekannt (vgl. insbesondere erstinstanzliches Urteil S. 29 ff.).
Zusammenfassend ist festzuhalten, dass die genannten Indizien für sich allein betrachtet zwar nur mit einer gewissen Wahrscheinlichkeit auf das Wissen des Beschwerdeführers um den Drogentransport hinweisen. In ihrer Gesamtheit erbringen sie jedoch - wie die Vorinstanz willkürfrei erwägen konnte - vollen Beweis. Die Schlussfolgerung im angefochtenen Urteil, es bestünden bei objektiver Betrachtung keine offensichtlich erheblichen bzw. schlechterdings nicht zu unterdrückenden Zweifel an der Schuld des Beschwerdeführers, verletzt damit kein Bundesrecht.
2.5.3 Im Übrigen hat sich die Vorinstanz im angefochtenen Urteil mit den wesentlichen Vorbringen des Beschwerdeführers auseinandergesetzt und die Protokolle der Telefongespräche, wie dargelegt, ausführlich gewürdigt. Entgegen der Auffassung des Beschwerdeführers liegt daher auch keine Missachtung seines Anspruchs auf rechtliches Gehör vor.
3. 3.1 Der Beschwerdeführer bringt vor, der Organisator und Drahtzieher des Drogentransports im Hintergrund, der Mann namens "P._", habe nicht verhaftet und damit auch nicht befragt werden können. Indem die Vorinstanz trotzdem auf dessen Aussagen in den überwachten Telefongesprächen abgestellt habe, habe sie sein Recht, einem Belastungszeugen Fragen zur Person und zur Sache stellen zu können, verletzt. Hierin liege ein Verstoss gegen Art. 6 Abs. 3 lit. d EMRK respektive gegen <ref-law> begründet (Beschwerde S. 22 f.).
3.2 Mit der vom Beschwerdeführer angerufenen Garantie von Art. 6 Ziff. 3 lit. d EMRK soll ausgeschlossen werden, dass ein Strafurteil auf Aussagen von Zeugen abgestützt wird, ohne dass der beschuldigten Person wenigstens einmal angemessene und hinreichende Gelegenheit gegeben wird, das Zeugnis in Zweifel zu ziehen und Fragen an den Zeugen zu stellen. Die beschuldigte Person muss namentlich in der Lage sein, die Glaubhaftigkeit einer Aussage prüfen und den Beweiswert in kontradiktorischer Weise auf die Probe und in Frage stellen zu können. Dieser Anspruch wird als Konkretisierung des rechtlichen Gehörs gemäss <ref-law> auch durch <ref-law> geschützt (vgl. zum Ganzen <ref-ruling> E. 2; <ref-ruling> E. 2.2; <ref-ruling> E. 4.2; <ref-ruling> E. 6c/cc). Aussagen von Zeugen und Auskunftspersonen dürfen demnach in der Regel nur nach erfolgter Konfrontation zum Nachteil einer beschuldigten Person verwertet werden. Dem Anspruch, den Belastungszeugen Fragen zu stellen, kommt insofern grundsätzlich absoluter Charakter zu (BGE <ref-ruling> E. 2.2; <ref-ruling> E. 3.1; Niklaus Oberholzer, Grundzüge des Strafprozessrechts, 2. Aufl., 2005, N. 432).
Unter besonderen Umständen kann jedoch auf eine Konfrontation der beschuldigten Person mit dem Belastungszeugen oder auf die Einräumung der Gelegenheit zu ergänzender Befragung des Zeugen verzichtet werden (ausführlich hierzu <ref-ruling> E. 5b mit Hinweisen). Dies ist insbesondere der Fall, wenn der Zeuge berechtigterweise das Zeugnis verweigert, er trotz angemessener Nachforschung unauffindbar bleibt, oder wenn er verstirbt. Es ist diesfalls gestützt auf Art. 6 Ziff. 3 lit. d EMRK jedoch notwendig, dass die beschuldigte Person dazu hinreichend Stellung nehmen kann, die Aussagen sorgfältig geprüft werden und ein Schuldspruch nicht alleine darauf abgestützt wird (BGE <ref-ruling> E. 2.2 mit Hinweisen; <ref-ruling> E. 5b).
3.3 Vorliegend kann offen gelassen werden, ob sich der Beschwerdeführer in Bezug auf die Auswertung von Protokollen überwachter Telefongespräche überhaupt auf Art. 6 Abs. 3 lit. d EMRK berufen kann (vgl. hierzu das Urteil des Bundesgerichts 1P.704/1994 vom 27. Juni 1995 E. 2b, wonach grundsätzlich kein zu Art. 6 Ziff. 3 lit. d EMRK analoger Grundrechtsanspruch auf Gegenüberstellung mit den einzelnen Teilnehmern der abgehörten Gespräche besteht). Selbst wenn dies der Fall sein sollte, so liegt jedenfalls keine Verletzung der genannten Bestimmung vor. Der Beschwerdeführer geht selbst davon aus, dass die Person namens "P._" trotz angemessener Nachforschung unauffindbar geblieben ist und deshalb nicht als Zeuge unter Wahrung der Teilnahmerechte des Beschwerdeführers befragt werden konnte. Des Weiteren wurde dem Beschwerdeführer die Möglichkeit eingeräumt, zu den von "P._" am Telefon gemachten Aussagen Stellung zu beziehen. Wie die Vorinstanz jedoch, wie dargelegt, willkürfrei festgestellt hat, ist der Einwand des Beschwerdeführers, es liege seitens von "P._" eine Verwechslung vor, nicht stichhaltig. Schliesslich wird der Schuldspruch vorliegend nach sorgfältiger Prüfung der im Rahmen der Telefongespräche von "P._" gemachten Aussagen nicht einzig auf diese abgestützt.
4. 4.1 Der Beschwerdeführer wendet sich schliesslich gegen die Strafzumessung. Er bringt vor, während die erste Instanz von einer Drogenmenge von rund zehn Kilogramm ausgegangen sei, werde im angefochtenen Urteil auf sechs Kilogramm abgestellt. Dass die Vorinstanz trotz dieser Reduktion um 40% die Strafe verglichen mit dem erstinstanzlichen Urteil nicht herabgesetzt habe, verletze das Verschlechterungsverbot. Zudem erscheine es unangemessen, bei einem bloss eventualvorsätzlich handelnden Ersttäter und Transporteur von netto 720 Gramm Heroin eine Einsatzstrafe von vier Jahren zu verhängen (Beschwerde S. 24 ff.).
4.2 Soweit der Beschwerdeführer eine Verletzung des Verschlechterungsverbots rügt, ist seiner Beschwerde kein Erfolg beschieden.
Das Verbot, ein Urteil, das nur von der verurteilten Person angefochten wird, zu deren Nachteil abzuändern (Verschlechterungsverbot; Verbot der reformatio in peius), ergibt sich primär aus dem kantonalen Prozessrecht. Es zählt nicht zu den verfassungsmässigen Rechten des Bundes oder der Kantone und lässt sich nicht aus der EMRK herleiten (vgl. Urteil des Bundesgerichts 6B_411/2007 vom 2. November 2007 E. 1.3).
Das Verschlechterungsverbot ist in <ref-law>/SG verankert. Nach dieser Bestimmung darf grundsätzlich keine schärfere Bestrafung erfolgen, wenn einzig die beschuldigte Person Berufung erhoben hat. Eine reformatio in peius läge somit vor, wenn die obere Instanz eine schwerere Strafe ausgefällt hätte als die untere Instanz. Dies ist vorliegend nicht der Fall, da die Vorinstanz die Berufung abgewiesen und damit die im erstinstanzlichen Urteil ausgesprochene Freiheitsstrafe von 41⁄2 Jahren bestätigt hat.
Zu prüfen bleibt jedoch, ob dieses Strafmass, wie der Beschwerdeführer behauptet, Bundesrecht verletzt.
4.3 Die Vorinstanz hat im Strafzumessungspunkt erwogen, die vom Beschwerdeführer transportierte Drogenmenge sei beträchtlich. Der Beschwerdeführer sei in Übereinstimmung mit dem erstinstanzlichen Urteil als nicht klassischer Drogenkurier (Bodypacker, Schlucker), sondern als Spediteur mit Verfügungsgewalt über Weg, Zeitpunkt und Versteck einzustufen. Angemessen erscheine eine Einsatzstrafe von vier Jahren, selbst wenn hinsichtlich der Menge nur noch von mindestens sechs Kilogramm Heroingemisch auszugehen sei. Ansatzpunkt für die Strafzumessung bilde nämlich die Einordnung des Beschwerdeführers innerhalb des Verteilnetzes. Die Drogenmenge werde dagegen nur als eines unter mehreren Kriterien berücksichtigt und verliere an Bedeutung je deutlicher der Grenzwert im Sinne von <ref-law> überschritten sei. Straferhöhend zu berücksichtigen sei die mehrfache Widerhandlung gegen das ANAG. Insgesamt erscheine eine Freiheitsstrafe von 41⁄2 Jahren schuldangemessen (angefochtenes Urteil S. 8 f.).
4.4 Nach <ref-law> misst das Gericht die Strafe nach dem Verschulden des Täters zu. Es berücksichtigt das Vorleben, die persönlichen Verhältnisse sowie die Wirkung der Strafe auf das Leben der schuldigen Person. Die Bewertung des Verschuldens wird in Abs. 2 dahingehend präzisiert, dass dieses nach der Schwere der Verletzung oder Gefährdung des betroffenen Rechtsguts, nach der Verwerflichkeit des Handelns, den Beweggründen und Zielen des Täters sowie danach bestimmt wird, wie weit der Täter nach den inneren und äusseren Umständen in der Lage war, die Gefährdung oder Verletzung zu vermeiden. Es liegt im Ermessen des Sachgerichts, in welchem Umfang es die verschiedenen Strafzumessungsfaktoren berücksichtigt. Die Strafrechtliche Abteilung greift auf Beschwerde in Strafsachen hin nur in die Strafzumessung ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wenn sie wesentliche Gesichtspunkte ausser Acht gelassen bzw. falsch gewichtet hat (<ref-ruling> E. 2.1; vgl. zum bisherigen Recht: <ref-ruling> E. 6.1; <ref-ruling> E. 2; <ref-ruling> E. 4a).
4.5 Die Vorinstanz hat in ihren Urteilserwägungen sämtliche relevanten rechtlichen und tatsächlichen Gesichtspunkte berücksichtigt. Die vom Beschwerdeführer transportierte Menge von mindestens sechs Kilogramm Heroingemisch bzw. - ausgehend von einem Reinheitsgrad von 12% - von mindestens 720 Gramm reinem Heroin ist sehr beträchtlich und überschreitet den für die Qualifikation als schweren Fall erforderlichen Grenzwert von 12 Gramm reinem Heroin um ein Vielfaches. Des Weiteren hat die Vorinstanz die Rolle des Beschwerdeführers als Spediteur mit Verfügungsgewalt, welcher sich insoweit von einem klassischen Drogenkurier unterscheidet, korrekt gewürdigt.
Im Übrigen ist die vom Beschwerdeführer gemachte Gegenüberstellung der Drogenmengen von rund zehn Kilogramm gemäss erstinstanzlichem Urteil verglichen mit rund sechs Kilogramm im zweitinstanzlichen Urteil verkürzt. Die erste Instanz lastete dem Beschwerdeführer an, am 19. Februar 2004 drei Kilogramm und am 14. März 2004 6,868 Kilogramm Heroingemisch in die Schweiz transportiert zu haben. Die Vorinstanz hob demgegenüber hervor, ob der Beschwerdeführer am 19. Februar 2004 tatsächlich genau drei Kilogramm Heroingemisch transportiert und übergeben habe, könne nicht abschliessend und zweifelsfrei festgestellt werden. Dies könne aber dahingestellt bleiben, zumal jedenfalls mit an Sicherheit grenzender Wahrscheinlichkeit davon auszugehen sei, dass es sich um eine Menge von namhafter Bedeutung bzw. um eine Menge im Bereich einer schweren Widerhandlung gegen das BetmG gehandelt habe (angefochtenes Urteil S. 7). Vom Transport vom 14. März 2004 rechnete sie ihm jene 5,868 Kilogramm Heroingemisch zu, welche sich in den Konservendosen in der Reisetasche befanden. Die Vorinstanz bezog mithin abweichend zum erstinstanzlichen Urteil einzig das sich in der Mittelkonsole des Fahrzeugs befindliche Heroingemisch von rund einem Kilogramm nicht in ihre Berechnung mit ein, da sich diese Drogen dem Beschwerdeführer nicht zurechnen liessen. Die Vorinstanz ging folglich von einer Drogenmenge von 5,868 Kilogramm zuzüglich einer "Menge von namhafter Bedeutung" aus.
Insgesamt gesehen ist die von der Vorinstanz in Übereinstimmung mit der ersten Instanz ausgefällte Strafe von 41⁄2 Jahren zwar als hoch einzustufen. Das Strafmass bewegt sich jedoch innerhalb des dem Sachgericht bei der Strafzumessung zukommenden Ermessensspielraums.
4.6 Zusammenfassend ist das angefochtene Urteil somit auch im Strafzumessungspunkt nicht zu beanstanden. Da die Vorinstanz die kantonale Berufung damit zu Recht abgewiesen hat, ist nicht einsichtig und wird vom Beschwerdeführer auch nicht näher substanziiert, weshalb es Bundesrecht verletzen sollte, ihm die Kosten des Berufungsverfahrens vollumfänglich aufzuerlegen.
5. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Kantonsgericht St. Gallen, Strafkammer, schriftlich mitgeteilt.
Lausanne, 4. August 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Stohner