Sachverhalt: A. Das Strafgericht des Kantons Basel-Stadt sprach mit Urteil vom 10. Februar 2006 X._, Y._ sowie Z._ des gewerbsmässigen Betrugs und der mehrfachen Urkundenfälschung schuldig und verurteilte sie zu Zuchthausstrafen von 3 ? (X._), 3 ? (Y._) und 2 ? Jahren (Z._). In einigen Anklagepunkten sprach das Strafgericht die Angeklagten vom Vorwurf des Betrugs sowie von der Anklage der Geldwäscherei, ferner X._ in einem Fall vom Vorwurf der Urkundenfälschung frei. Im Anklagepunkt der mehrfachen Geldwäscherei, begangen vor dem 10. Februar 1999, stellte es das Verfahren wegen Eintritts der Verfolgungsverjährung ein. Die Zivilforderungen der A._Bank, der B._Bank sowie der C._Bank verwies es auf den Zivilweg. B. X._, Y._ und Z._ appellierten gegen dieses Urteil beim Appellationsgericht des Kantons Basel-Stadt. Dieses stellte in Nebenpunkten der Anklage den Verjährungseintritt fest und sprach Z._ in einem weiteren Nebenpunkt vom Betrugsvorwurf frei. Ansonsten bestätigte das Appellationsgericht die vorinstanzlichen Schuldsprüche. Es bestrafte X._ mit einer Freiheitsstrafe von 3 ? Jahren, Y._ mit einer Freiheitsstrafe von 2 Jahren und 10 Monaten, wovon 2 Jahre unter Gewährung des bedingten Strafvollzugs bei einer Probezeit von 2 Jahren, sowie Z._ mit einer Freiheitsstrafe von 2 Jahren und 3 Monaten, wovon 1 ? Jahre unter Gewährung des bedingten Strafvollzugs, bei einer Probezeit von 2 Jahren. C. X._ (Beschwerdeführer 1) und Z._ (Beschwerdeführer 2) erheben Beschwerde in Strafsachen beim Bundesgericht. Sie beantragen, das vorinstanzliche Urteil sei aufzuheben, und sie seien von den Vorwürfen des gewerbsmässigen Betrugs und der mehrfachen Urkundenfälschung freizusprechen. Eventuell seien die ausgesprochenen Strafen deutlich zu reduzieren, und es sei beiden Beschwerdeführern der bedingte Strafvollzug zu bewilligen. Subeventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen mit dem Auftrag, den Fall im Sinne der Erwägungen des Bundesgerichts neu zu beurteilen. D. Die von Y._ beim Bundesgericht eingereichte Beschwerde in Strafsachen bildet Gegenstand des Verfahrens 6B_12/2010. E. Es wurden keine Vernehmlassungen eingeholt. 