Sachverhalt:
A. Gegen X._ und weitere Mitangeklagte wurde im Kanton Basel-Stadt ein Strafverfahren wegen Verdachts diverser Straftaten zum Nachteil der A._AG (heute B._AG) eingeleitet. Der Anklage liegt folgender Sachverhalt zugrunde:
Der Mitangeklagte Y._ war in der Zeit, als die frühere A._AG in Basel das D._Projekt erstellte, innerhalb der Firma unter anderem Leiter der Sparte Gesamtleistungen Gebäude. Sein Untergebener X._ war seit April 2001 Gesamtprojekt-Manager des D._Projekts. Im Mai 2002 wurde ihm mitgeteilt, dass er zusätzlich zu seiner Tätigkeit am D._ Projekt auch noch die Leitung der E._Unternehmung übernehmen sollte. Dazu war er lediglich unter der Voraussetzung bereit, dass ihm zusätzliche Leistungen seitens der Arbeitgeberin zugesichert würden. So kam es am 30. Juni 2002 zu einer Vereinbarung über die neuen Anstellungsbedingungen, die der damalige CEO der A._AG, Z._, sowie Y._ und X._ unterzeichneten. Danach standen Letzterem neu eine Gehaltserhöhung und die Aufnahme in das Bonusprogramm zu. Ausserdem verpflichtete sich die A._AG zur Übernahme der Kosten für die Anschaffung eines neuen Privatwagens im Wert von rund Fr. 80'000.--. Da sich X._ mit diesen Leistungen nicht zufrieden geben wollte, wurde ihm - so die Anklage - von Y._ ein Bargeldbetrag von Fr. 30'000.-- übergeben, wodurch er sich der Hehlerei schuldig gemacht haben soll. Weiter habe sich X._ mit Wissen und im Einverständnis von Y._ zwei Rechnungen über je knapp Fr. 20'000.-- für den Ausbau seiner privaten Eigentumswohnung durch die A._AG bezahlen lassen. Die Anklage wirft ihm insoweit mehrfachen Betrug, eventualiter mehrfache ungetreue Geschäftsbesorgung sowie mehrfache Urkundenfälschung vor. Schliesslich soll er sich, so die Anklage, auch des Steuerbetrugs schuldig gemacht haben. Er habe den Steuerbehörden für das Jahr 2002 einen inhaltlich unwahren Lohnausweis eingereicht, indem die von der A._AG übernommenen Kosten des privaten Personenwagens zum Preis von Fr. 82'540.50 zum Einkommen jenes Jahres gezählt hätten, im Lohnausausweis indes nicht ausgewiesen worden seien.
B. Das Strafgericht Basel-Stadt sprach X._ am 24. August 2007 von den Vorwürfen der Hehlerei, des mehrfachen Betrugs, der mehrfachen ungetreuen Geschäftsbesorgung, der mehrfachen Urkundenfälschung und des Steuerbetrugs kostenlos frei. Die gegen ihn erhobene Schadenersatzforderung der B._AG verwies es auf den Zivilweg.
C. Auf Appellation der Staatsanwaltschaft des Kantons Basel-Stadt hin verurteilte das Appellationsgericht des Kantons Basel-Stadt X._ mit Urteil vom 24. Oktober 2008 wegen Hehlerei, mehrfacher ungetreuer Geschäftsbesorgung, mehrfacher Urkundenfälschung und Steuerbetrugs zu einer bedingten Geldstrafe von 240 Tagessätzen à Fr. 200.-- bei einer Probezeit von zwei Jahren. Im Übrigen bestätigte das Appellationsgericht, abgesehen vom Kostenentscheid, das erstinstanzliche Urteil.
D. Dagegen gelangt X._ mit Beschwerde an das Bundesgericht. Er verlangt die Aufhebung des Urteils des Appellationsgerichts und seine Freisprechung in sämtlichen Anklagepunkten. Eventualiter sei das angefochtene Urteil aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Der Beschwerde sei ferner die aufschiebende Wirkung zu erteilen.
E. Mit Präsidialverfügung vom 10. Februar 2009 ist der Beschwerde die aufschiebende Wirkung superprovisorisch zuerkannt worden.
F. Die Staatsanwaltschaft des Kantons Basel-Stadt beantragt in ihrer Stellungnahme vom 2. April 2009 die Beschwerdeabweisung. Das Appellationsgericht des Kantons Basel-Stadt hat am 15. April 2009 auf eine Stellungnahme zur Beschwerde verzichtet. Der Beschwerdeführer hat mit Schreiben vom 29. April 2009 unaufgefordert Stellung zur Vernehmlassung der Staatsanwaltschaft des Kantons Basel-Stadt genommen.

Erwägungen:
1. 1.1 Der Hehlerei im Sinne von Art. 160 StGB macht sich schuldig, wer eine Sache, von der er weiss oder annehmen muss, dass sie ein anderer durch eine strafbare Handlung gegen das Vermögen erlangt hat, erwirbt, sich schenken lässt, zum Pfande nimmt, verheimlicht oder veräussern hilft.
1.2 Der Beschwerdeführer wendet sich im Rahmen des objektiven Tatbestands gegen die Annahme der Vorinstanz, Y._ habe ihm Bargeld in der Höhe von Fr. 30'000.-- übergeben. Aus den Akten gehe einzig hervor, dass solches beabsichtigt gewesen sei. Nach der Übergabe besagten Bargeldbetrags von C._, dem Leiter Finanzen und Controlling, an Y._ verlaufe die Spur des Geldes im Sand. Y._ könne sich an die Weitergabe des Geldbetrags an ihn, den Beschwerdeführer, nicht erinnern, obgleich er sie selbst vorgenommen haben soll. Aus den weiteren von der Vorinstanz beigezogenen Beweisen bzw. Indizien ergebe sich nichts anderes. Insbesondere liege auch kein Dokument, wie beispielsweise eine Quittung, vor, welches die Geldübergabe belegen würde. Bei dieser Sachlage festzustellen, dass ihm Fr. 30'000.-- ausgehändigt worden seien, verstosse gegen das Willkürverbot und die Unschuldsvermutung (Beschwerde, S. 8-14).
1.3 Die Rüge der Verletzung der Unschuldsvermutung gemäss Art. 32 Abs. 1 BV und Art. 6 Ziff. 2 EMRK begründet der Beschwerdeführer damit, dass seine Verurteilung auf einer willkürlichen Beweiswürdigung beruhe (Beschwerde, S. 13). Sie hat damit vorliegend keine selbständige Bedeutung. Wurden die Beweise willkürlich zu seinen Lasten gewürdigt, ist seine Verurteilung bereits aus diesem Grund ohne weiteres aufzuheben. Zu prüfen ist somit allein, ob die Vorinstanz den Sachverhalt offensichtlich unrichtig (Art. 97 Abs. 1 BGG) bzw. willkürlich (Art. 9 BV; <ref-ruling> E. 1.2.2) festgestellt hat. 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; <ref-ruling> E. 2a; <ref-ruling> E. 2a m. H.)
1.4 Die Vorinstanz hält die Bargeldzahlung von Fr. 30'000.-- an den Beschwerdeführer für erwiesen. Sie stützt sich dabei in erster Linie auf die Aussagen von Y._. Dieser hat zu Protokoll gegeben, dass der Beschwerdeführer für die Übernahme der Doppelfunktion Forderungen gestellt und unter anderem einen Mercedes und Bargeld verlangt habe. Er, Y._, habe daher mit Z._, dem CEO, gesprochen. Dieser habe bezüglich dem Auto zugestimmt, mehr sei indessen "nicht drin" gewesen (kantonale Akten, S. 394). Der Beschwerdeführer sei damit nicht einverstanden gewesen. Er, Y._, habe sich deshalb überlegt, wie er den Beschwerdeführer zum Bleiben motivieren könne. Einerseits sei das Bargeld in der Höhe von Fr. 30'000.-- gewesen (kantonale Akten, S. 418). Der Beschwerdeführer habe gewusst, dass er, Y._, mit Z._ wegen der Geldforderung nicht einig geworden sei. Nun habe er das Geld doch bekommen, wobei er, Y._, nicht mehr wisse, ob er dem Beschwerdeführer gegenüber die Herkunft desselben offengelegt habe (kantonale Akten, S. 395). Ausgehend hievon sowie gestützt auf das Schreiben von Y._ an den Leitenden Staatsanwalt vom 25. August 2005, woraus der Bargeldfluss an den Beschwerdeführer wiederum unmissverständlich hervorgeht, nimmt die Vorinstanz an, dass die umstrittene Bargeldzahlung an den Beschwerdeführer tatsächlich stattgefunden hat, zumal auch die weiteren Indizien - so etwa die Aussagen von C._ und Z._ sowie der handschriftliche Vermerk auf dem Rechnungsbeleg vom 3. Juli 2002 über Fr. 35'000.-- ("30'000 X._, 5'000 C._ gm Y._") - für dieses Beweisergebnis sprächen und der Beschwerdeführer erstmals anlässlich der Appellationsverhandlung ernsthaft bestritten habe, das Bargeld erhalten zu haben. Im früheren Verfahrensverlauf habe er sich daran bloss nicht mehr erinnern können, habe eine solche Bargeldzahlung aber auch nicht ausschliessen mögen (vgl. angefochtenen Entscheid, S. 4 f.).
1.5 Was der Beschwerdeführer dagegen vorbringt, ist nicht geeignet, die Verfassungsmässigkeit der vorinstanzlichen Beweiswürdigung in Frage zu stellen. So findet seine Behauptung, Y._ habe die Übergabe des Geldes an ihn nicht zu bestätigen vermocht bzw. sich daran nicht erinnern können, in den Akten keine Stütze. Es ist zwar richtig, dass Y._ ausgesagt hat, er könne sich "an die Transaktion mit Geld aus dem Jura" nicht erinnern (kantonale Akten, S. 394). Seine Aussage bezieht sich jedoch, wie sich aus ihrem Kontext ergibt, entgegen der Beschwerde nicht auf die zur Diskussion stehende Geldübergabe an den Beschwerdeführer, die sich im Übrigen aus den oben wiedergegebenen Aussagen von Y._ und seinem Schreiben an die Staatsanwaltschaft ohne weiteres willkürfrei ableiten lässt, sondern vielmehr auf die entsprechende Geldbeschaffung über das Profitcenter Jura betreffend den Verkauf eines der A._AG gehörenden Inventargegenstands. Insoweit erweist sich die Beschwerde als unbegründet.
Ebenso wenig vermag der Beschwerdeführer mit seinen weiteren Einwänden gegen die vorinstanzliche Würdigung der übrigen Beweise und Indizien Willkür darzutun. Mit seinen Argumenten legt er nur dar, wie diese aus seiner Sicht richtigerweise zu würdigen gewesen wären, bleibt indessen den Nachweis schuldig, dass und weshalb die vorinstanzliche Beweiswürdigung unhaltbar sein soll. Dies gilt etwa für seine Ausführungen, aus den Aussagen von Z._ könne nicht abgeleitet werden, dass Y._ auch diesem gegenüber eine Bargeldübergabe von Fr. 30'000.-- an den Beschwerdeführer eingestanden habe, denn die fraglichen Äusserungen des CEO beträfen entgegen der Auffassung der Vorinstanz nicht die Übergabe des Bargeldbetrags, sondern die Verantwortlichkeit bzw. Befugnis betreffend die Ausrichtung zusätzlicher Leistungen an den Beschwerdeführer (vgl. kantonale Akten, S. 492). Eine solche Auslegung der Aussagen von Z._ kann zwar nicht als vollständig aus der Luft gegriffen abgetan werden, sie ist aber auch keineswegs zwingend. Vielmehr hat die Vorinstanz die Aussagen des CEO angesichts des Sachzusammenhangs, in dem sie erfolgten, ohne weiteres so verstehen dürfen, wie sie es im angefochtenen Entscheid getan hat. Im Übrigen verliert sich der Beschwerdeführer mit seinen weiteren Vorbringen zur Interpretation der Aussagen von Z._ (suggestive Fragestellung durch die Staatsanwaltschaft, Hinstellen der Bargeldübergabe als Faktum) in nicht substantiierten Behauptungen, mit denen sich Willkür nicht begründen lässt.
Nichts anderes gilt schliesslich für die Einwendungen betreffend die vorinstanzliche Würdigung der Aussagen von C._, des handschriftlichen Vermerks auf dem Rechnungsbeleg vom 3. Juli 2002 sowie seiner eigenen Aussagen. Mit seinen diesbezüglichen Argumenten vermag der Beschwerdeführer allenfalls darzulegen, weshalb die Beweise bzw. Indizien aus seiner Sicht nicht genügen, die Bargeldübergabe an ihn als tatsächlich erfolgt anzusehen, nicht aber, dass die gegenteilige Auffassung der Vorinstanz offensichtlich unhaltbar oder willkürlich ist.
1.6 Der Beschwerdeführer wendet sich auch gegen die Annahme des subjektiven Tatbestands. Angesichts des aus seiner Sicht nicht abschliessenden Charakters der Vereinbarung vom 30. Juni 2002 und aufgrund der Spitzenposition von Y._ als Mitglied der Geschäftsleitung und des Verwaltungsrats des Konzerns habe er davon ausgehen dürfen, dass dessen Zusicherungen und Leistungen an ihn legal und im Sinne der Geschäftsleitung erfolgten. Er habe deshalb nicht annehmen müssen, dass das Bargeld von Fr. 30'000.-- aus einer strafbaren Handlung von Y._ gegen das Vermögen der A._AG stamme. Die gegenteilige Annahme der Vorinstanz kritisiert er mit verschiedenen Argumenten als bundesrechtswidrig (Beschwerde, S.14- 19).
1.7 Der subjektive Tatbestand der Hehlerei erfordert Vorsatz, wobei Eventualvorsatz genügt. Der Wortlaut der Bestimmung verlangt, dass der Täter weiss oder annehmen muss, dass die Sache durch eine strafbare Handlung erlangt worden ist (Art. 160 Ziff. 1 StGB). Die Formulierung des Gesetzes ist im Sinne einer Beweisregel gegen nahe liegende Ausreden zu verstehen und soll den Rückschluss von der Kenntnis der Verdachtsgründe auf den Willen des Täters, sich über diese hinwegzusetzen, erleichtern (vgl. STRATENWERTH/JENNY, Schweizerisches Strafrecht, Bes. Teil I, 6. Aufl., Bern 2003, § 20 N 19; WEISSENBERGER, BSK-Strafrecht II, 2. Aufl., Basel 2007, Art. 160 Ziff. 68). Nach der Rechtsprechung zu Art. 144 aStGB reicht es aus, wenn Verdachtsgründe die Möglichkeit einer strafbaren Vortat nahelegen. Danach genügt für den Vorsatz die Feststellung, dass der Täter im Sinne einer Parallelwertung in der Laiensphäre die Verdachtsgründe kannte, die ihm die Überzeugung von der deliktischen Herkunft der Sache aufdrängen mussten, und dass er die Tat auch für diesen Fall vornahm (BGE 69 IV 68; <ref-ruling> E. 2).
1.8 Die Annahme der Vorinstanz, der Beschwerdeführer habe um die deliktische Herkunft des ihm übergebenen Bargelds im Sinne von Art. 160 StGB wissen müssen, ist nicht zu beanstanden. Hierfür sprechen - was die Vorinstanz im angefochtenen Entscheid nachvollziehbar darlegt - die Vertragsvereinbarung vom 30. Juni 2002, welche die bewilligten zusätzlichen finanziellen Leistungen der Arbeitgeberin an den Beschwerdeführer im Detail wiedergibt, die Unterzeichnung des Vertragswerks durch den CEO Z._, Y._ und den Beschwerdeführer, dessen Kenntnis darüber, dass die Geschäftsleitung bzw. der CEO Z._ seiner (weiteren) Forderung nach Bargeld nicht entsprechen wollte, sowie die Art und Weise der Zuwendung von barem Geld in der Höhe von Fr. 30'000.-- nur gerade kurze Zeit nach der Vereinbarungsunterzeichnung vom 30. Juni 2002. Was der Beschwerdeführer gegen den Schluss des "Annehmen-Müssens" einwendet, richtet sich einzig gegen die vorinstanzliche Beweiswürdigung. Dabei legt er im Grunde nur dar, wie die Beweise, insbesondere die zitierte Vertragsvereinbarung sowie die Stellung von Y._ bzw. dessen Befugnisse innerhalb des Unternehmens, aus seiner Sicht zu würdigen gewesen wären. Die blosse Darlegung der eigenen Sichtweise des Geschehens ist jedoch nicht geeignet, eine offensichtlich unrichtige Feststellung des Sachverhalts darzutun. Denn für die Begründung von Willkür genügt praxisgemäss nicht, dass das angefochtene Urteil mit der Darstellung des Beschwerdeführers nicht übereinstimmt oder eine andere Lösung oder Würdigung vertretbar erscheint oder gar vorzuziehen wäre (<ref-ruling> E. 2b mit Hinweisen). Im Übrigen zeigt der Beschwerdeführer nicht auf, dass und inwiefern die Vorinstanz von einem bundesrechtswidrigen Begriff des Eventualvorsatzes ausgegangen sein sollte. Die Beschwerde ist daher abzuweisen, soweit darauf überhaupt eingetreten werden kann.
2. 2.1 Der ungetreuen Geschäftsbesorgung im Sinne von Art. 158 Ziff. 1 Abs. 1 StGB macht sich schuldig, wer aufgrund des Gesetzes, eines behördlichen Auftrags oder eines Rechtsgeschäfts damit betraut ist, Vermögen eines andern zu verwalten oder solche Vermögensverwaltungen zu beaufsichtigen und dabei unter Verletzung von Pflichten bewirkt oder zulässt, dass der andere am Vermögen geschädigt wird. In subjektiver Hinsicht genügt Eventualvorsatz. Dieser muss sich auf Tatmittel, Erfolg und Kausalzusammenhang richten. Als Qualifikationsgrund tritt in Art. 158 Ziff. 1 Abs. 3 StGB das Handeln unter Bereicherungsabsicht hinzu. Unter unrechtmässiger Bereicherung ist nach der Rechtsprechung jede wirtschaftliche Besserstellung zu verstehen, auf die ihr Empfänger keinen Rechtsanspruch besitzt (<ref-ruling> E. 2b).
Gemäss Art. 251 StGB macht sich der Urkundenfälschung bzw. der Falschbeurkundung schuldig, wer in der Absicht, jemanden am Vermögen oder an andern Rechten zu schädigen oder sich oder einem andern einen unrechtmässigen Vorteil zu verschaffen, eine rechtlich erhebliche Tatsache unrichtig beurkundet oder beurkunden lässt. Der subjektive Tatbestand erfordert - neben der Schädigungs- oder Vorteilsabsicht - Vorsatz, wobei Eventualvorsatz genügt.
2.2 Der Beschwerdeführer erhebt insoweit keine Einwände, als die Vorinstanz den objektiven Tatbestand der ungetreuen Geschäftsbesorgung durch Bezahlenlassen privater Rechnungen aus dem Umbau des Eigenheims zu Lasten der A._AG und denjenigen der Falschbeurkundung durch Visieren und Falschkontierenlassen dieser Rechnungen sowie Integrieren der inhaltlich unwahren Belege in die Konzernbuchhaltung als erfüllt ansieht. Er wehrt sich indessen in beiden Fällen gegen die Annahme des subjektiven Tatbestands. So habe er nicht mit den jeweils erforderlichen Bereicherungs- bzw. Schädigungsabsichten gehandelt, weil er davon ausgegangen sei, Anspruch auf die zusätzliche Entschädigung für die Übernahme der Doppelfunktion zu haben. Ferner habe er sich darüber im Irrtum befunden, dass Y._ nicht im Interesse und in Vertretung der A._AG gehandelt habe. Damit habe er sich - was letztlich den Vorsatz ausschliesse - über das Vorhandensein einer Einwilligung der A._AG betreffend die Abgeltung seiner Lohnforderungen durch das Bezahlen von Privatrechnungen im Sinne von Art. 13 StGB geirrt bzw. über die Möglichkeit der Zurechnung einer Einwilligung von Y._ an die A._AG (Beschwerde, S. 20-25).
2.3 Was der Täter wusste, wollte und in Kauf nahm (<ref-ruling> E. 2b) bzw. ob er in der Absicht handelte, sich zu bereichern (<ref-ruling> E. 3), einen unrechtmässigen Vorteil zu erlangen (<ref-ruling> E. 2 S. 178) oder jemanden zu schädigen, betrifft so genannte innere Tatsachen und ist damit Tatfrage. Gleich verhält es sich mit der Frage, ob der Täter in einer irrigen Vorstellung über den Sachverhalt im Sinne von Art. 13 StGB gehandelt hat (vgl. SCHOTT, Bundesgerichtsgesetz, Basler Kommentar, 2008, Art. 95 N. 29; SCHWERI, Eidgenössische Nichtigkeitsbeschwerde in Strafsachen, Bern 1993, S. 207 Ziff. 659 und 660).
2.4 Mit seinen Einwendungen nimmt der Beschwerdeführer erneut eine eigene Beweiswürdigung vor und setzt sich über die vorinstanzlichen Feststellungen zum inneren Sachverhalt hinweg, ohne dass sich aus seinen Ausführungen ergäbe, dass und inwiefern die Beweiswürdigung der Vorinstanz willkürlich und ihre Feststellungen offensichtlich unrichtig wären (Art. 105 i.V.m. Art. 97 Abs. 1 BGG; <ref-ruling> E. 1.4.3). Auf die Beschwerde ist insoweit nicht einzutreten.
2.5 Die Vorinstanz stellt fest, dass in der Privatwirtschaft Leistungen an Arbeitnehmer auch durch Übernahme von Privatrechnungen möglich sei. Eine derartige Übernahme setze jedoch die Einwilligung des Geschäftsherrn voraus. Ohne eine solche sei und bleibe der Vorgang eine Schädigung des zu schützenden Vermögens. Dass Y._ in die Schädigung der Firma eingewilligt habe, vermöge den Beschwerdeführer nicht zu entlasten. Hierüber habe er auch nicht im Zweifel sein können, denn er habe konkret gewusst, dass der CEO der A._AG, Z._, die im Zusammenhang mit dem Funktionswechsel gestellten Forderungen nur teilweise akzeptiert, im Übrigen aber abgelehnt habe. Somit habe der Beschwerdeführer nicht darüber irren können, dass er die ihm gemäss Art. 158 StGB auferlegten Pflichten habe verletzen dürfen. Es sei denn auch bezeichnend, dass die inkriminierten Rechnungen keine Hinweise auf den wirklichen Auftraggeber und die Baustelle enthielten, womit einigermassen offensichtlich werde, dass dieser diskrete Weg gewählt worden sei, weil sich der Beschwerdeführer und Y._ bewusst gewesen seien, dass Z._ mit diesen Sonderleistungen nicht einverstanden gewesen wäre.
2.6 Ausgehend hievon, insbesondere mit Blick darauf, dass sich der Beschwerdeführer darüber im Klaren war, womit Z._ einverstanden gewesen ist und womit nicht, verletzt es kein Bundesrecht, wenn die Vorinstanz vor dem Hintergrund seiner "Vertuschungsaktionen" zum Schluss gelangt, dass vorliegend kein Raum für einen Irrtum verbleibt, und sie annimmt, der Beschwerdeführer habe in Bezug auf die Pflichtverletzungen gegenüber seiner Arbeitgeberin, der A._AG, und dem Eintritt der Vermögensschädigung vorsätzlich und - da kein anderer Grund für sein Tun erkennbar ist - mit Bereicherungsabsicht gehandelt. Die Anwendung des qualifizierten Tatbestands von Art. 158 Ziff. 1 Abs. 3 StGB ist somit nicht zu beanstanden. Aus den gleichen Gründen, d.h. weil der Beschwerdeführer gewusst hat, dass Z._ nicht mehr konzedieren wollte als mit der schriftlichen Vereinbarung vom 30. Juni 2002 zugestanden, durfte die Vorinstanz auch in Bezug auf Art. 251 StGB ohne Bundesrechtsverletzung annehmen, dass der Beschwerdeführer mit seinem Verhalten die Verfälschung der Konzernbuchhaltung in Kauf genommen und mit Schädigungsabsicht zu Lasten der Arbeitgeberin gehandelt hat. Die Beschwerde erweist sich daher auch in diesem Punkt als unbegründet, soweit darauf überhaupt eingetreten werden kann.
3. 3.1 Gemäss Art. 186 Abs. 1 DBG (SR 642.11) wird wegen Steuerbetrugs bestraft, wer zum Zwecke einer Steuerhinterziehung im Sinne von Artikel 175-177 gefälschte, verfälschte oder inhaltlich unwahre Urkunden wie Geschäftsbücher, Bilanzen, Erfolgsrechnungen oder Lohnausweise und andere Bescheinigungen Dritter zur Täuschung gebraucht. Im Falle eines Steuerbetrugs im Bereich der direkten Bundessteuer sind Art. 186 ff. DBG anwendbar, bei solchen im Bereich der kantonalen Steuern Art. 59 StHG (SR.642.14) oder die gestützt darauf erlassenen kantonalen Tatbestände, hier § 223 des Steuergesetzes des Kantons Basel-Stadt (StG, SG 640.100).
3.2 Die Vorinstanz hat den Beschwerdeführer wegen Steuerbetrugs im Sinne von Art. 186 DBG und § 223 StG/BS verurteilt. Der von der A._AG finanzierte Personenwagen im Wert von rund Fr. 82'000.-- sei in das Eigentum des Beschwerdeführers übergegangen und stelle eine geldwerte Leistung der Arbeitgeberin dar. Die Anschaffungskosten hätten daher im Lohnausweis 2002 nicht fehlen dürfen. Indem der Beschwerdeführer den Steuerbehörden diesen inhaltlich unwahren Lohnausweis eingereicht habe, habe er den Tatbestand schuldhaft erfüllt. Der Beschwerdeführer kritisiert das vorinstanzliche Urteil in verschiedener Hinsicht als nicht stichhaltig. So sei fraglich, ob ein Lohnausweis überhaupt den Begriff der "unwahren Urkunde" erfülle. Sodann stelle die Vorinstanz willkürlich und unter Verletzung des Grundsatzes "in dubio pro reo" fest, dass er im Jahre 2002 Eigentümer des von der A._AG finanzierten Personenwagens geworden sei. Schliesslich unterlasse es die Vorinstanz, die subjektive Seite von Art. 186 Abs. 1 DBG und § 223 des kantonalen Steuergesetzes zu prüfen (Beschwerde, S. 26-37).
3.3 Der objektive Tatbestand des Steuerbetrugs ist erfüllt, wenn der Steuerpflichtige im Steuerveranlagungsverfahren zur Erlangung eines fiskalischen Vorteils von unechten oder inhaltlich unwahren Urkunden Gebrauch macht. Die Verwendung der Urkunden muss zum Zweck der Täuschung der Steuerbehörde erfolgen. Ob der Täter die Urkunde dabei selber gefälscht oder verfälscht hat, ist unmassgeblich, ebenso, ob der "Drittfälscher" selber strafbar ist oder nicht (<ref-ruling>). Nach dem gemeinen Urkundenstrafrecht kommt Lohnausweisen - worauf in der Beschwerde zutreffend hingewiesen wird - in der Regel keine erhöhte Glaubwürdigkeit zu (<ref-ruling> E. 2a). Im Verkehr mit den Steuerbehörden stellen sie allerdings Urkunden dar, welche geeignet sind, die Wahrheit darin festgehaltener Sachverhalte zu gewährleisten (vgl. DONATSCH, Kommentar zum Schweizerischen Steuerstrafrecht, Bundesgesetz über die direkte Bundessteuer (DBG), 2. Aufl., Basel 2008, Art. 186 N. 8, 26, 31; RICHNER/FREI/KAUFMANN, Handkommentar zum DBG, Zürich 2003, Art. 186 N. 4 und 26 u.a. mit Hinweis auf ZR 57/1958 Nr. 92; siehe auch 6S.733/1996 E. 2c/aa). Denn gegenüber diesen Behörden besteht im Rahmen der Steuerveranlagung die besondere gesetzliche Pflicht zur wahrheitsgetreuen Deklarierung. Die Vorinstanz geht daher zu Recht davon aus, dass dem Lohnausweis 2002, welcher der Beschwerdeführer den kantonalen Steuerbehörden im Veranlagungsverfahren einreichte, Urkundencharakter zukommt. Auf ihre zutreffenden Ausführungen kann verwiesen werden.
3.3 Der objektive Tatbestand des Steuerbetrugs ist erfüllt, wenn der Steuerpflichtige im Steuerveranlagungsverfahren zur Erlangung eines fiskalischen Vorteils von unechten oder inhaltlich unwahren Urkunden Gebrauch macht. Die Verwendung der Urkunden muss zum Zweck der Täuschung der Steuerbehörde erfolgen. Ob der Täter die Urkunde dabei selber gefälscht oder verfälscht hat, ist unmassgeblich, ebenso, ob der "Drittfälscher" selber strafbar ist oder nicht (<ref-ruling>). Nach dem gemeinen Urkundenstrafrecht kommt Lohnausweisen - worauf in der Beschwerde zutreffend hingewiesen wird - in der Regel keine erhöhte Glaubwürdigkeit zu (<ref-ruling> E. 2a). Im Verkehr mit den Steuerbehörden stellen sie allerdings Urkunden dar, welche geeignet sind, die Wahrheit darin festgehaltener Sachverhalte zu gewährleisten (vgl. DONATSCH, Kommentar zum Schweizerischen Steuerstrafrecht, Bundesgesetz über die direkte Bundessteuer (DBG), 2. Aufl., Basel 2008, Art. 186 N. 8, 26, 31; RICHNER/FREI/KAUFMANN, Handkommentar zum DBG, Zürich 2003, Art. 186 N. 4 und 26 u.a. mit Hinweis auf ZR 57/1958 Nr. 92; siehe auch 6S.733/1996 E. 2c/aa). Denn gegenüber diesen Behörden besteht im Rahmen der Steuerveranlagung die besondere gesetzliche Pflicht zur wahrheitsgetreuen Deklarierung. Die Vorinstanz geht daher zu Recht davon aus, dass dem Lohnausweis 2002, welcher der Beschwerdeführer den kantonalen Steuerbehörden im Veranlagungsverfahren einreichte, Urkundencharakter zukommt. Auf ihre zutreffenden Ausführungen kann verwiesen werden.
3.4 3.4.1 Die Beurteilung der inhaltlichen Richtigkeit des den Steuerbehörden eingereichten Lohnausweises 2002 hängt vorliegend von der zivilrechtlichen Vorfrage ab, ob der von der A._AG erworbene Personenwagen im Wert von rund Fr. 82'000.-- in das Eigentum des Beschwerdeführers übergegangen ist. Zur Übertragung von Fahrniseigentum bedarf es nach schweizerischem Recht neben einem gültigen Grundgeschäft des Übergangs des Besitzes auf den Erwerber (Art. 714 Abs. 1 ZGB). Ausgehend von der Vereinbarung vom 30. Juni 2002, aus welcher sich explizit ergibt, dass die Arbeitgeberin die Kosten für die Anschaffung eines "neuen Privat-PW" für den Beschwerdeführer übernimmt, gelangt die Vorinstanz in sorgfältig abwägender Würdigung aller massgeblichen Umstände zum Schluss, dass es sich beim besagten Fahrzeug, welches sich noch immer im Besitz des Beschwerdeführers befindet, nicht um einen Geschäftswagen bzw. um ein Firmenauto der A._AG handelt, sondern um ein von ihr finanziertes Privatfahrzeug, an welchem der Beschwerdeführer Eigentum erworben hat.
3.4.2 Was der Beschwerdeführer in tatsächlicher Hinsicht gegen die Beweiswürdigung der Vorinstanz vorbringt, erschöpft sich (erneut) in rein appellatorischer und damit unzulässiger Kritik am angefochtenen Urteil. So schildert er einzig seine eigene abweichende Sichtweise, indem er darlegt, wie die von der Vorinstanz herangezogenen Beweise und Indizien - etwa die Vertragsvereinbarung vom 30. Juni 2002, die Aussagen von Y._, Z._ oder C._, die buchhalterische Erfassung des Personenwagens sowie die Tatsachen, dass der Fahrzeugausweis auf den Namen des Beschwerdeführers lautet, er Versicherungsnehmer der Fahrzeugversicherung ist und das in seinem Besitz befindliche Auto trotz Ausscheidens aus der A._AG vor Jahren noch immer nutzt etc. - richtigerweise zu würdigen gewesen wären, ohne dabei allerdings substantiiert aufzuzeigen, inwiefern die vorhandenen Beweise andere Schlussfolgerungen geradezu aufdrängen und die Beweiswürdigung der Vorinstanz (auch) im Ergebnis offensichtlich unhaltbar ist (<ref-ruling> E. 1.4). Auf eine solche Kritik ist nicht einzutreten. Ebenso wenig ergibt sich aus der Beschwerde, dass und inwiefern der Schluss der Vorinstanz, wonach der Beschwerdeführer das von der A._AG finanzierte Personenfahrzeug im Jahre 2002 zu Eigentum erworben hat, bundesrechtswidrig sein sollte. Solches ist auch nicht ersichtlich, zumal keine Anhaltspunkte für irgendeine nachträgliche abweichende Vereinbarung vorliegen. Dass die A._AG mit dem Beschwerdeführer seit seinem Firmenaustritt im Jahre 2004 über die Konditionen der Übernahme des "Geschäftswagens" verhandeln soll, ist in diesem Zusammenhang entgegen der Beschwerde unerheblich (vgl. insoweit auch kantonale Akten, S. 1096 ff., 1099, wonach sich die A._AG in ihrer Rechtsschrift an das Strafgericht BS vom 7. August 2007 auf den Standpunkt stellt, der Personenwagen sei in das Eigentum des Beschwerdeführers übergegangen). Es kann deshalb offenbleiben, ob es sich dabei, wie der Beschwerdeführer meint, um ein Novum im Sinne von Art. 99 Abs. 1 BGG handelt.
3.5 Ist somit der Beschwerdeführer im Jahre 2002 Eigentümer des fraglichen Personenwagens geworden, hätten die von der A._AG übernommenen Kosten für die Anschaffung des Autos als geldwerte Leistung der Arbeitgeberin im Lohnausweis des Beschwerdeführers klarerweise nicht fehlen dürfen. Dennoch hat der Beschwerdeführer diesen inhaltlich unwahren Lohnausweis der Steuerverwaltung eingereicht und damit im Rahmen von rund Fr. 82'000.-- unvollständige Angaben über sein Einkommen aus unselbständiger Tätigkeit gemacht. Insoweit hat er nach zutreffender Ansicht der Vorinstanz den objektiven Tatbestand des Steuerbetrugs erfüllt. Dass die Vorinstanz auch den subjektiven Tatbestand als gegeben ansieht, sie also davon ausgeht, dass der Beschwerdeführer vorsätzlich und mit der erforderlichen Hinterziehungs- und Täuschungsabsicht gehandelt hat, ergibt sich - wenn auch nicht ausdrücklich, so doch implizit - aus den Erwägungen im angefochtenen Entscheid. Von einer mangelnden Sachverhaltsfeststellung bzw. einer unzureichenden Begründung im Sinne von Art. 29 Abs. 2 BV kann deshalb nicht gesprochen werden. Lediglich einer besseren Begründung wegen wird ein Urteil aber nicht aufgehoben. Da keinerlei Anhaltspunkte dafür vorliegen, dass sich der Beschwerdeführer über die inhaltliche Richtigkeit des Lohnausweises geirrt haben könnte, hat die Vorinstanz den subjektiven Tatbestand, was sich aus der Sache ergibt, zu Recht bejaht. Der Schuldspruch wegen Steuerbetrugs im Sinne von Art. 186 DBG und § 223 StG/BS verletzt mithin kein Bundesrecht. Daran ändert nichts, dass die Steuerverwaltung des Kantons Basel-Stadt, die Nach- und Strafsteuerverfahren offensichtlich eingestellt hat, zumal es sich nach der bundesgerichtlichen Rechtsprechung bei Steuerhinterziehung und Steuerbetrug um echt konkurrierende Tatbestände handelt (vgl. <ref-ruling>; vgl. DONATSCH, a.a.O., Art. 186 N. 49 ff.; ROGER CADOSCH, Bundesgesetz über die direkte Bundessteuer, 2. Aufl., Zürich 2008, Art. 186 N. 1) und der Strafrichter hinsichtlich der Frage, ob ein Steuerbetrug vorliegt, nicht an den Entscheid der Steuerverwaltung gebunden ist, ob und wie ein bestimmter Vermögenswert zu versteuern ist (vgl. angefochtenen Entscheid, S. 13).
4. Die Beschwerde ist damit abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Kosten (Art. 66 Abs. 1 BGG). Mit dem Entscheid in der Sache ist das Gesuch um aufschiebende Wirkung gegenstandslos geworden.

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 Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 14. Mai 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Arquint Hill