Sachverhalt:
A. Die Personalfürsorgestiftung X._ AG in Liquidation (Beschwerdegegnerin) klagte beim Zivilgericht Basel-Stadt gegen A._ sowie weitere Personen auf Zahlung von Fr. 10 Mio. nebst Zins und Kosten aus aktienrechtlicher Verantwortlichkeit.
Im Rahmen dieses Zivilprozesses beantragte A._, die Beschwerdegegnerin sei als Klägerin zur Leistung einer Prozesskaution für seine ausserordentlichen Kosten im Betrag von Fr. 355'596.50 zu verpflichten, wobei eine spätere Nachdeckung vorzubehalten sei. Eventualiter sei die Beschwerdegegnerin zu verpflichten, eine Erklärung des Sicherheitsfonds BVG beizubringen, wonach dieser für eine allfällig zugesprochene Parteientschädigung aufkommen werde. Das Zivilgericht wies diese Begehren mit Verfügung vom 11. März 2008 ab und setzte A._ Frist zur Klagebeantwortung an.
B. Mit Urteil vom 21. April 2008 wies das Appellationsgericht des Kantons Basel-Stadt eine von A._ gegen die Verfügung vom 11. März 2008 erhobene Verfügung ab.
Am 22. Mai 2008 verstarb A._.
C. Mit Eingabe vom 9. Juni 2008 erklärten die Rechtsvertreter von A._ dem Bundesgericht, das Urteil des Appellationsgerichts Basel-Stadt vom 21. April 2008 im Namen des Erblassers, seiner Erben, seines Willensvollstreckers bzw. seines Nachlasses (nachfolgend gemeinsam: die Beschwerdeführer) mit Beschwerde in Zivilsachen und subsidiärer Verfassungsbeschwerde anfechten zu wollen. Die Beschwerdeführer beantragen hauptsächlich, es sei das angefochtene Urteil aufzuheben und die Beschwerdegegnerin im Verfahren vor dem Zivilgericht Basel-Stadt zur Leistung der verlangten Prozesskaution, eventualiter zur Beibringung einer Erklärung des Sicherheitsfonds BVG, zu verpflichten. Zudem wurde der Erlass vorsorglicher Massnahmen sowie die Sistierung des bundesgerichtlichen Verfahrens beantragt.
Die Beschwerdegegnerin sowie die Vorinstanz haben sich zum Ersuchen um Anordnung vorsorglicher Massnahmen sowie zu den verschiedenen von den Beschwerdeführern gestellten Verfahrensanträgen geäussert. Zur Beschwerde selbst wurden keine Vernehmlassungen eingeholt.
D. Mit Verfügung vom 28. Juli 2008 wies das Bundesgericht das Gesuch um Anordnung einer vorsorglichen Massnahme ab und sistierte das bundesgerichtliche Verfahren. Die Rechtsvertreter der Beschwerdeführer wurden zudem ersucht, das Bundesgericht so bald als möglich über den Antritt oder die Ausschlagung der Erbschaft in Kenntnis zu setzen bzw. eine amtliche Erbenbescheinigung und gegebenenfalls eine Vollmacht der Erben einzureichen.
Mit Eingabe vom 18. Dezember 2008 beantragten die Rechtsvertreter im Namen von F._, St. Gallen, unter anderem, dieser sei als Willensvollstrecker im Nachlass von A._ als Partei in eigenem Namen vorzumerken und die Sistierung des Verfahrens sei aufzuheben.
Mit Verfügung vom 27. Februar 2009 wurden die Rechtsvertreter der Beschwerdeführer aufgefordert, dem Bundesgericht per 9. März 2009 die Namen der Erben des verstorbenen A._ mitzuteilen und eine allfällige Bevollmächtigung nachzuweisen.
Mit Schreiben vom 9. März 2009 teilten die Rechtsvertreter dem Bundesgericht mit, dass es sich bei den designierten Erben um B._, C._, D._ sowie E._ handle. Dabei liessen sie zunächst offen, ob diese die Rechtsvertreter ebenfalls zur Vertretung im bundesgerichtlichen Verfahren bevollmächtigen werden. Mit Eingabe vom 24. März 2009 wurden dem Bundesgericht die Vollmachten der aufgeführten Erben eingereicht.

Erwägungen:
1. Mit dem Entscheid in der Sache wird das Gesuch um Erlass vorsorglicher Massnahmen vom 18. Dezember 2008, mit dem die Beschwerdeführer die vom Bundesgericht bereits mit Verfügung vom 28. Juli 2008 abgelehnten Anträge wiederholen, gegenstandslos.
1.1 Die Beschwerde wurde sowohl im Namen des Erblassers A._, dessen Erben, des Willensvollstreckers F._ sowie in demjenigen des Nachlasses eingereicht, die alle von denselben Anwälten vertreten werden.
Dem Erblasser A._ sowie dem Nachlass fehlt es bereits an der Parteifähigkeit (vgl. <ref-ruling> E. 1.2.1 S. 306 sowie E. 1.2.4 S. 310; <ref-ruling> E. 1 S. 143). Auf ihre Beschwerden ist demnach nicht einzutreten.
1.2 Der Willensvollstrecker hat aufgrund seiner gesetzlichen Stellung in eigenem Namen die Nachlassrechte zu wahren. Nach ständiger Rechtsprechung des Bundesgerichts ist er in Prozessen um die Aktiven und die Passiven der Erbschaft Partei, soweit ihm gemäss <ref-law> die Verwaltung der betreffenden Erbschaftswerte zusteht (<ref-ruling> E. 4.2 S. 117; <ref-ruling> E. 3a S. 133 f.; <ref-ruling> E. 1 S. 144). F._, der seine Rechtsvertreter gehörig bevollmächtigt hat, steht demnach als Willensvollstrecker die Befugnis zur Prozessführung als Partei zu. Dies wird auch von der Beschwerdegegnerin nicht in Abrede gestellt.
Die Beschwerdegegnerin macht jedoch geltend, die vier Erben, die dem Bundesgericht ebenfalls eine Vollmacht eingereicht haben, seien neben dem Willensvollstrecker als Parteien vorzumerken, da bei Unklarheit darüber, ob die Nachlasswerte für die Erfüllung der eingeklagten Forderung genügten, auch die Erben eingeklagt werden bzw. Beklagte bleiben müssten. Nur so bestehe auch eine persönliche Haftung der Erben. Wie es sich damit verhält, kann vorliegend offengelassen werden, steht doch im bundesgerichtlichen Beschwerdeverfahren zunächst lediglich die Verweigerung der Auferlegung einer Prozesskaution an die Beschwerdegegnerin zur Diskussion. Über die von der Beschwerdegegnerin aufgeworfene Frage, ob das Nachlassvermögen zur Erfüllung der geltend gemachten Verantwortlichkeitsansprüche genügt bzw. ob neben dem Willensvollstrecker auch die Erben als beklagte Parteien am Verantwortlichkeitsprozess teilzunehmen haben, wird im Rahmen der Fortführung des erstinstanzlichen Verfahrens zu befinden sein.
2. Nach <ref-law> können den Nachlass betreffende Prozesse - mit Ausnahme von dringenden Fällen - weder fortgesetzt noch angehoben werden. Entsprechend sistierte das Bundesgericht das Beschwerdeverfahren mit Verfügung vom 28. Juli 2008, bis über den Antritt der Erbschaft entschieden sei.
Mit Eingabe vom 18. Dezember 2008 beantragte der Willensvollstrecker dem Bundesgericht, es sei die Sistierung des Verfahrens aufzuheben, da nach seiner Vormerkung als Partei kein Grund mehr für die angeordnete Sistierung bestehe. Mit Schreiben vom 9. März 2009 teilten die Rechtsvertreter der Beschwerdeführer dem Bundesgericht die Namen der vier Erben mit und legten dar, dass noch nicht entschieden sei, ob diese den Nachlass annehmen oder ausschlagen sollten, was wiederum vom Ausgang der Verantwortlichkeitsklage abhänge. Der Bezirksschreiberei werde demnächst ein Gesuch um Erstreckung der Annahme- bzw. Ausschlagungsfrist bis zur rechtskräftigen Erledigung des Prozesses gestellt werden.
Von der Dringlichkeit eines Prozesses ist unter anderem dann auszugehen, wenn der Entschluss der Erben über die Annahme oder die Ausschlagung von der prozessualen Abklärung über bestimmte Verpflichtungen abhängig ist (TUOR/PICENONI, Berner Kommentar, 2. Aufl. 1964, N. 5 zu <ref-law>; ESCHER, Zürcher Kommentar, 3. Aufl. 1960, N. 8 zu <ref-law>; KURT WISSMANN, in: Basler Kommentar, Zivilgesetzbuch II, 3. Aufl. 2007, N. 6 zu <ref-law>; vgl. auch <ref-ruling> E. 2.3 S. 243). Diese Voraussetzung ist vorliegend gegeben, weshalb das bundesgerichtliche Beschwerdeverfahren in Anwendung von <ref-law> fortzuführen ist.
3. Die Beschwerde in Zivilsachen ist zulässig gegen Endentscheide, mithin solche, die das Verfahren abschliessen (vgl. dazu <ref-ruling> E. 1.1), sei es insgesamt (<ref-law>), sei es hinsichtlich eines Teils der gestellten, unabhängig von den anderen beurteilbaren Begehren oder für einen Teil der Streitgenossen (<ref-law>).
Mit dem vorliegend angefochtenen Urteil vom 21. April 2008 wies das Appellationsgericht des Kantons Basel-Stadt die Beschwerde gegen die Verweigerung der Sicherstellung der ausserordentlichen Kosten des Erblassers ab. Dieser Entscheid schliesst das Verfahren weder insgesamt noch teilweise ab, wie dies in der Beschwerde vorgebracht wird, sondern stellt einen Zwischenentscheid dar.
3.1 Gegen selbständig eröffnete Vor- und Zwischenentscheide, die weder die Zuständigkeit noch den Ausstand betreffen, ist die Beschwerde nur zulässig, wenn eine der folgenden alternativen Voraussetzungen erfüllt ist: Erstens, wenn der Zwischenentscheid einen nicht wieder gutzumachenden Nachteil bewirken kann (<ref-law>). Zweitens, wenn die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit und Kosten für ein weitläufiges Beweisverfahren ersparen würde (<ref-law>). Letztere Voraussetzung ist vorliegend offensichtlich nicht gegeben und wird in der Beschwerde auch nicht geltend gemacht.
Die selbständige Anfechtbarkeit von Vor- und Zwischenentscheiden bildet aus prozessökonomischen Gründen eine Ausnahme vom Grundsatz, dass sich das Bundesgericht mit jeder Angelegenheit nur einmal befassen soll (<ref-ruling> E. 2.2 S. 191; <ref-ruling> E. 2.1 S. 631). Die Ausnahme ist restriktiv zu handhaben, zumal die Parteien keiner Rechte verlustig gehen, wenn sie einen Vor- bzw. Zwischenentscheid im Sinne von <ref-law> nicht selbständig anfechten, können sie ihn doch mit dem Endentscheid anfechten, soweit er sich auf dessen Inhalt auswirkt (<ref-law>).
3.2 In der Beschwerde wird zum behaupteten nicht wieder gutzumachenden Nachteil (<ref-law>) ausgeführt, die Anfechtung des Entscheids des Appellationsgerichts sei die einzige Möglichkeit, die Frage der Vereinbarkeit der Abweisung des Kautionsbegehrens mit dem Bundesrecht jemals vom Bundesgericht überprüfen zu lassen. Selbst wenn der Zwischenentscheid mit dem Endentscheid angefochten werden könnte, erginge ein allfälliges Urteil des Bundesgerichts immer zu spät: Selbst bei Gutheissung einer Beschwerde könne der mit dem Kautionsbegehren verfolgte Zweck, nämlich die Sicherstellung künftiger Anwaltskosten, nicht mehr erreicht werden, da diese Kosten dannzumal längst angefallen wären. Es könne jedoch nicht Sinn und Zweck des Bundesgerichtsgesetzes sein, die Frage von der bundesgerichtlichen Prüfung auszunehmen, ob Entscheide über Kautionsleistungen mit dem Bundesrecht vereinbar seien.
3.3 Ein nicht wieder gutzumachender Nachteil im Sinne von <ref-law> muss nach der bundesgerichtlichen Rechtsprechung rechtlicher Natur sein, was voraussetzt, dass er durch einen späteren günstigen Entscheid nicht oder nicht mehr vollständig behoben werden kann (<ref-ruling> E. 2.1 S. 190; <ref-ruling> E. 2.3.1 S. 632; je mit Hinweisen). Rein tatsächliche Nachteile, etwa die Verlängerung oder Verteuerung des Verfahrens, fallen demgegenüber nicht in Betracht (<ref-ruling> E. 2.2 S. 191 mit Hinweisen).
Vorliegend machen die Beschwerdeführer im Zusammenhang mit der als bundesrechtswidrig gerügten Verweigerung der beantragten Sicherstellung der Anwaltskosten durch die Beschwerdegegnerin nicht bloss einen tatsächlichen Nachteil in Form einer Verteuerung des Verfahrens geltend. Sie berufen sich vielmehr auf einen verfahrensrechtlichen Anspruch auf Sicherstellung, der ihnen von der Vorinstanz versagt worden sei. Ein solcher Nachteil ist rechtlicher Natur und kann auch mit einem für die Beschwerdeführer günstigen Endentscheid nicht mehr behoben werden, zumal die Kosten zu diesem Zeitpunkt bereits angefallen wären, jedoch trotz zugesprochener Parteientschädigung gegebenenfalls ungedeckt blieben. Der vorgebrachte Nachteil tritt zwar nur dann ein, wenn die Beschwerdegegnerin im hängigen Verantwortlichkeitsprozess unterliegt, ihr eine Parteientschädigung auferlegt wird und deren Bezahlung ausbleibt. Dies kann jedoch nicht ausgeschlossen werden. Nach der bundesgerichtlichen Rechtsprechung genügt die blosse Möglichkeit eines rechtlichen Nachteils (<ref-ruling> E. 2.1 S. 191).
3.4 Die Beschwerde in Zivilsachen ist grundsätzlich zulässig und auf die ebenfalls erhobene subsidiäre Verfassungsbeschwerde ist nicht einzutreten (<ref-law>).
4. Die Beschwerdeführer machen zunächst unter Hinweis auf die verschiedenen Prozessordnungen der übrigen Kantone bzw. des Bundes sowie den Gesetzgebungsprozess im Rahmen der Vereinheitlichung des Zivilprozessrechts geltend, der Kautionsgrund der Zahlungsunfähigkeit sei ein allgemein anerkannter Bestandteil des Zivilprozessrechts der Schweiz.
Die Beschwerdeführer verkennen mit ihren Vorbringen, dass es im heutigen Zeitpunkt kein "Zivilprozessrecht der Schweiz" gibt, aus dem sich ein für sämtliche Zivilverfahren geltender Kautionsgrund der Zahlungsunfähigkeit ableiten liesse. Zwar ist die Gesetzgebung auf dem Gebiet des Zivilprozessrechts nach <ref-law> Sache des Bundes. Die gestützt auf diese Bestimmung von der Bundesversammlung verabschiedete Schweizerische Zivilprozessordnung vom 19. Dezember 2008 (Zivilprozessordnung, ZPO; BBl 2009 21) ist jedoch noch nicht in Kraft. Demnach ist für den vor dem Zivilgericht Basel-Stadt hängigen Verantwortlichkeitsprozess nach wie vor die Zivilprozessordnung des Kantons Basel-Stadt vom 8. Februar 1875 (ZPO/BS; GS 221.100) massgebend. Darüber hinaus lässt sich weder aus der Tatsache, dass andere Kantone einen Kautionsgrund für Zahlungsunfähigkeit der klagenden Partei kennen noch aus dem Umstand, dass sich der Kanton Basel-Stadt im Rahmen des Vernehmlassungsverfahrens zur Schweizerischen Zivilprozessordnung nicht ablehnend zu Art. 88 des Vorentwurfs vom Juni 2003 geäussert habe, etwas zu Gunsten der Beschwerdeführer ableiten.
Entgegen der in der Beschwerde geäusserten Ansicht lässt sich das beantragte Sicherstellungsbegehren de lege lata nicht auf einen in der Schweiz allgemein geltenden Kautionsgrund der Zahlungsunfähigkeit stützen.
5. Die Beschwerdeführer rügen weiter eine willkürliche Auslegung (<ref-law>) der Zivilprozessordnung des Kantons Basel-Stadt.
5.1 Sie berufen sich auf ein fundamentales Prinzip, wonach die unterliegende Partei Gerichts- und Anwaltskosten der Gegenseite zu tragen habe. Entgegen der Ansicht der Vorinstanz könne aus <ref-law>/BS nicht abgeleitet werden, dass in der basel-städtischen Zivilprozessordnung das Verursacherprinzip nicht gelte. Vielmehr enthalte die Bestimmung eine Regelung für den Fall, dass das Verursacherprinzip aus Gründen der Zahlungsunfähigkeit der Klagpartei nicht vollumfänglich durchgezogen werden könne, und zwar dahingehend, dass grundsätzlich derjenige für die Kosten aufzukommen habe, welcher einer hablosen Partei den Prozess finanziere, nicht die Gegenpartei. Zudem handle es sich bei der von der Vorinstanz erwähnten Bestimmung, wonach der Staat einer Partei, die gegen einen im Kostenerlass prozessierenden Gegner obsiegt, dann keine Parteientschädigung bezahlen müsse, wenn diese vermögend sei (<ref-law>/BS), lediglich um eine Ausnahme von der Regel des Verursacherprinzips.
Das Kostenrisiko der Gegenpartei steige gemäss <ref-law>/BS nur dann, wenn sie sehr vermögend sei und es der Allgemeinheit deswegen nicht zugemutet werden könne, dass der Staat eine ihr allenfalls zugesprochene Parteientschädigung übernehme. Es treffe aber nicht zu, dass <ref-law>/BS eine Regelung enthalte, nach der die Gegenpartei eines im Kostenerlass prozessierenden Klägers von vornherein keine Aussicht auf eine Parteientschädigung habe; im Gegenteil garantiere der Staat grundsätzlich dafür. Weil der Staat für die Kosten einer im Kostenerlass prozessierenden Partei garantiere, so die Beschwerdeführer weiter, liege auch auf der Hand, dass diese Partei keine Kaution zu leisten habe. Deshalb sei es unhaltbar, wenn die Vorinstanz aus <ref-law>/BS ableiten wolle, die basel-städtische Zivilprozessordnung spreche sich gegen eine Kautionspflicht bei Zahlungsunfähigkeit aus. Wenn eine Staatsgarantie bestehe, brauche es keine Kaution.
5.2 Willkürlich ist ein Entscheid nach konstanter Rechtsprechung nicht schon dann, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre. Das Bundesgericht hebt einen kantonalen Entscheid wegen Willkür vielmehr nur auf, wenn er offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.1 S. 211; <ref-ruling> E. 2 S. 61, 467 E. 3.1 S. 473 f.; je mit Hinweisen). Dabei genügt es nicht, wenn sich nur die Begründung des angefochtenen Entscheides als unhaltbar erweist. Eine Aufhebung rechtfertigt sich nur dann, wenn der Entscheid auch im Ergebnis verfassungswidrig ist (<ref-ruling> E. 4.1 S. 133; <ref-ruling> E. 2.1 S. 211; je mit Hinweisen).
5.3 Die Beschwerdeführer vermögen den angefochtenen Entscheid nicht als willkürlich auszuweisen. Insbesondere ist nicht einzusehen, weshalb aus den Bestimmungen über den Kostenerlass nach <ref-law>/BS ein allgemein geltender Anspruch auf Sicherheitsleistung abzuleiten wäre. Wie die Vorinstanz zutreffend ausführt, steht den juristischen Personen das Recht auf Kostenerlass im Unterschied zu den natürlichen Personen grundsätzlich nicht zu. <ref-law>/BS bezieht sich auf die unentgeltliche Rechtspflege und die damit getroffenen Wertentscheidungen lassen nicht zwingend auf eine Kautionspflicht wegen Zahlungsunfähigkeit einer klagenden Partei schliessen, die - etwa weil es sich dabei um eine juristische Person handelt - keinen Kostenerlass geniesst. Auch aus dem von den Beschwerdeführern herangezogenen Grundsatz, wonach die unterliegende Partei die Anwaltskosten der Gegenseite zu tragen hat, ergibt sich nicht ohne weiteres ein allgemeiner Anspruch auf Sicherstellung dieser Kosten. Die Vorinstanz hat das kantonale Zivilprozessrecht jedenfalls nicht willkürlich ausgelegt, wenn sie die Auferlegung der beantragten Sicherheitsleistung mit der Begründung verweigerte, dass die basel-städtische Zivilprozessordnung den Kautionsgrund der fehlenden Zahlungsfähigkeit nicht kenne. Daran vermag auch der Hinweis der Beschwerdeführer auf die Schweizerische Zivilprozessordnung nichts zu ändern, die - wie bereits dargelegt - noch nicht in Kraft ist.
Die Vorinstanz hat mit nachvollziehbarer Begründung ausgeschlossen, dass das kantonale Recht über den Wortlaut von <ref-law>/BS hinaus eine Kautionspflicht der zahlungsunfähigen Partei kennt und damit das Bestehen einer Lücke im Sinne einer planwidrigen Unvollständigkeit verneint. Davon, dass die Vorinstanz diesen Schluss willkürlich gezogen hätte, kann keine Rede sein. Zudem verweisen die Beschwerdeführer hinsichtlich der Frage, wie die von ihnen behauptete Lücke zu schliessen wäre, lediglich auf ihre Ausführungen zu der nach ihrer Ansicht zutreffenden Auslegung der kantonalen Zivilprozessordnung, die sich als keineswegs zwingend erwiesen hat. Eine Verletzung des Willkürverbots (<ref-law>) ist nicht ersichtlich. Schliesslich wird mit der nicht näher begründeten Behauptung (vgl. <ref-law>), die Ablehnung einer Kautionspflicht bei Zahlungsunfähigkeit führe zu einem sachlich unbefriedigenden Resultat, keine willkürliche Rechtsanwendung dargetan.
Auf das Vorbringen, wonach eine Partei, die einer zahlungsunfähigen Partei einen Prozess finanziert, als Konsequenz des Verursacherprinzips einzustehen habe für eine allenfalls der Gegenseite zugesprochene Parteientschädigung, ist nicht näher einzugehen. Abgesehen davon, dass sich aus dem vorinstanzlich verbindlich festgestellten Sachverhalt (vgl. <ref-law>) nicht ergibt, dass die Beschwerdegegnerin als "zahlungsunfähige Hülle" im Verantwortlichkeitsprozess "vorgeschoben" worden wäre, wie dies in der Beschwerde behauptet wird, steht die Frage, ob ein Dritter den Beschwerdeführern für die Parteikosten haftet, vorliegend nicht zur Diskussion. Eine allfällige Haftung Dritter beschlägt nicht die Rechtmässigkeit der Verweigerung der Sicherheitsleistung und wäre von den Beschwerdeführern gegenüber der angeblich haftpflichtigen Partei geltend zu machen.
6. Die Beschwerdeführer machen sodann geltend, die von der Vorinstanz angewendete Gesetzesbestimmung (<ref-law>/BS) sei willkürlich.
Die Vorinstanz ist auf die entsprechenden Vorbringen nicht eingetreten, weil sie darin unter Berücksichtigung der übrigen Willkürrügen keine eigenständige Bedeutung erkennen konnte. Die Beschwerdeführer bringen zwar vor, zunächst eine willkürliche Rechtsanwendung und sodann Willkür in der Rechtssetzung geltend gemacht zu haben. Sie haben jedoch weder in der Beschwerde noch vor Bundesgericht dargetan, dass <ref-law>/BS an sich in stossender Weise dem Gerechtigkeitsgedanken zuwiderlaufe. Vielmehr berufen sie sich darauf, dass die erwähnte Bestimmung gegen das Willkürverbot verstosse, "wenn diese Bestimmung tatsächlich zulassen sollte, dass wie im vorliegenden Fall eine zahlungskräftige Partei, welche einen Prozess selber führen könnte, eine zahlungsunfähige Partei gerade so alimentiert, dass diese den Prozess zwar auf Rechnung der zahlungskräftigen Partei führen, aber eine allenfalls der Gegenseite zugesprochene Parteientschädigung nicht bezahlen kann".
Damit machen die Beschwerdeführer richtig besehen nicht geltend, der genannte Erlass lasse sich nicht auf ernsthafte sachliche Gründe stützen oder sei sinn- oder zwecklos (vgl. <ref-ruling> E. 3 S. 3 mit Hinweisen), sondern das Vorgehen der Gegenpartei bzw. des Sicherheitsfonds BVG verdiene aufgrund deren Zusammenwirkens im konkreten Fall keinen Rechtsschutz. Wie die Vorinstanz zutreffend erwog, ist eine eigenständige Bedeutung der erhobenen Willkürrüge nicht erkennbar.
7. Die Beschwerdeführer bringen vor, die Vorinstanz habe das Vorliegen eines Rechtsmissbrauchs (<ref-law>) zu Unrecht verneint.
7.1 Die Vorinstanz hat das Verhalten des Sicherheitsfonds BVG von vornherein nicht als rechtsmissbräuchlich erachtet. Sie hat dafür gehalten, dass der Sicherheitsfonds BVG aus aktienrechtlicher Verantwortlichkeit gegenüber den Beschwerdeführern im Unterschied zur Beschwerdegegnerin nicht primär anspruchsberechtigt sei. Der Sicherheitsfonds erleide durch eine Schädigung der Beschwerdegegnerin lediglich einen Reflexschaden, zu dessen Deckung er gemäss Art. 56a BVG (SR 831.40) "im Umfang der sichergestellten Leistungen in die Ansprüche der Vorsorgeeinrichtung [eintrete]". Bei dieser Sachlage sei es zum vornherein nicht rechtsmissbräuchlich, wenn der Sicherheitsfonds BVG die Beschwerdegegnerin insoweit unterstütze, dass diese zur Verminderung ihres Schadens selber einen Prozess führen könne.
7.2 Was die Beschwerdeführer gegen diese Erwägungen vorbringen, überzeugt nicht. Unabhängig von der Bürgschaftssituation, welche die Vorinstanz lediglich zur Veranschaulichung der Interessenlage erwähnte, wird im angefochtenen Entscheid zutreffend zum Ausdruck gebracht, dass der Sicherheitsfonds als möglicher Reflexgeschädigter durchaus ein legitimes Interesse daran haben kann, dass eine Vorsorgeeinrichtung ihren Schaden mittels Durchsetzung von Verantwortlichkeitsansprüchen begrenzt. Abgesehen davon, dass aus dem vorinstanzlich verbindlich festgestellten Sachverhalt (vgl. <ref-law>) weder hervorgeht, dass die Voraussetzungen für einen Direktanspruch des Sicherheitsfonds erfüllt wären, noch dass die Prozessführung durch die Beschwerdegegnerin einzig darauf angelegt ist, das Kostenrisiko des Sicherheitsfonds auf Kosten der Beschwerdeführer zu minimieren, ist vorliegend kein offenbarer Missbrauch eines Rechts (<ref-law>) ersichtlich (zu den von Lehre und Rechtsprechung entwickelten Fallgruppen <ref-ruling> E. 5.1 S. 497 f.; <ref-ruling> E. 2a S. 259; je mit Hinweisen). Auch die Beschwerdeführer stellen nicht in Abrede, dass ein allfälliger Verantwortlichkeitsanspruch zunächst der Beschwerdegegnerin zustehen würde. Ein offensichtlich gegen Treu und Glauben verstossendes Verhalten, das entgegen dem in der basel-städtischen Zivilprozessordnung fehlenden Kautionsgrund der Zahlungsunfähigkeit ausnahmsweise zur Auferlegung einer Sicherheitsleistung führen müsste, ist nicht erkennbar.
8. Die Beschwerdeführer rügen schliesslich eine Verletzung von <ref-law> sowie Art. 6 EMRK.
8.1 Sie bringen vor, sowohl aus <ref-law> als auch aus Art. 6 EMRK ergebe sich, dass sich beide Parteien eines Verfahrens grundsätzlich dem gleichen Kostenrisiko ausgesetzt sehen müssten. Es widerspreche dem Gleichheitsgebot, dem Gebot der gerechten Behandlung, dem Fairnessgebot und dem Gebot der Widerspruchsfreiheit, wenn die Beschwerdegegnerin aufgrund ihrer eigenen Zahlungsunfähigkeit kein Risiko trage, im Falle ihres Unterliegens effektiv eine Parteientschädigung ausrichten zu müssen.
8.2 Die Beschwerdeführer legen nicht näher dar, inwiefern sich aus den genannten Grundsätzen ein Anspruch auf Sicherheitsleistung der beklagten Partei in einem Zivilprozess ableiten liesse. Damit verfehlen sie die Begründungsanforderungen an eine Rüge der Verletzung verfassungsmässiger Rechte (Art. 106 Abs. 2 i.V.m. <ref-law>).
Entgegen ihrer Ansicht ist auch die Begründung der Vorinstanz nicht willkürlich, es sei nicht erkennbar, inwieweit die Verweigerung einer Prozesskaution den Anspruch auf gleiche und gerechte Behandlung verletzen solle. Auch wenn es zutrifft, dass es einen Unterschied darstellt, ob ein Kläger das Insolvenzrisiko des Beklagten trägt oder der Beklagte dasjenige des Klägers, da Letzterer bei Zweifeln an der Zahlungsfähigkeit der Gegenpartei auf eine Klage verzichten kann, so ist damit noch keine Ungleichbehandlung dargetan, aus der sich ein Kautionsgrund ableiten liesse, der in der kantonalen Verfahrensordnung nicht vorgesehen ist. Die unterschiedlichen Möglichkeiten von Kläger und Beklagtem, einer allfälligen Zahlungsunfähigkeit der Gegenpartei beim Entscheid über das prozessuale Vorgehen Rechnung zu tragen, ergeben sich ohne weiteres aus den unterschiedlichen Parteirollen im Zivilprozess. Ein Anspruch des Beklagten auf Sicherheitsleistung bei Zahlungsunfähigkeit des Klägers, sozusagen als Gegenstück zu dessen Entscheidungsfreiheit, gegebenenfalls auf eine Klage zu verzichten, ergibt sich nicht aus dem verfassungsrechtlichen Gleichbehandlungsgebot.
Unbehelflich ist auch der Hinweis der Beschwerdeführer auf Art. 6 EMRK. Sie übersehen, dass in den von ihnen zitierten Entscheiden des Bundesgerichts (<ref-ruling> E. 2.1 S. 137) sowie des Europäischen Gerichtshofs für Menschenrechte (Tolstoy gegen Grossbritannien vom 13. Juli 1955, Randnrn. 61 f.) nicht die Frage eines konventionsrechtlichen Anspruchs auf Sicherheitsleistung zu entscheiden war, sondern vielmehr, ob die Auferlegung einer Prozesskaution nach Massgabe von Art. 6 EMRK zulässig sei. Die Beschwerde erweist sich auch in dieser Hinsicht als unbegründet.
9. Auf die subsidiäre Verfassungsbeschwerde ist nicht einzutreten. Die Beschwerde in Zivilsachen erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Abs. 5 sowie Art. 68 Abs. 2 und Abs. 4 BGG). Der Beschwerdegegnerin, die sich mit Eingaben vom 14. Juli 2008 sowie 20. Januar 2009 zu den Gesuchen der Beschwerdeführer um Anordnung vorsorglicher Massnahmen hat vernehmen lassen, nicht jedoch zur Beschwerde selbst, wird eine reduzierte Parteientschädigung zugesprochen.

Demnach erkennt das Bundesgericht:
1. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
2. Die Beschwerde in Zivilsachen wird abgewiesen, soweit darauf einzutreten ist.
3. Die Gerichtskosten von Fr. 7'000.-- werden den Beschwerdeführern (unter solidarischer Haftung und intern zu gleichen Teilen) auferlegt.
4. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren (unter solidarischer Haftung und intern zu gleichen Teilen) mit Fr. 4'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 4. Mai 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann