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.