Sachverhalt: A. Die X._ Genossenschaft (Beklagte, Beschwerdegegnerin), ein bekanntes Schweizer Detailhandelsunternehmen, lancierte im April 2007 das Programm "Y._" für junge Familien mit Kindern. Im Oktober 2006 lud sie verschiedene Werbeagenturen ein, im Rahmen eines Wettbewerbs Gestaltungsvorschläge für die neue Produktelinie "Y._" einzureichen. Die Z._ Kommunikation AG (damals T._ AG) (Nebenintervenientin) machte den Vorschlag, einen roten Vari als Sympathieträger für das neue Programm zu verwenden. Zur zeichnerischen Umsetzung zog sie A._ und B._ (Kläger, Beschwerdeführer) bei. Der Wettbewerb wurde von der Nebenintervenientin mit der Figur "Roter Vari" gewonnen. Die Beklagte erteilte der Nebenintervenientin den Auftrag, das Logo "Y._" zu gestalten. Die weiteren Tierfiguren des Y._-Programms - "Zoo-Pasta" (nachfolgende Abbildungen b-f) und "Krokodil-Snack" (nachfolgende Abbildung g) - wurden im April 2007 geschaffen. Am 4. Januar 2007 übermittelte die Nebenintervenientin B._ den ersten Entwurf eines schriftlichen Rahmenvertrags, der schliesslich in überarbeiteter Form am 15./20. Juni 2007 unterzeichnet wurde. Darin verpflichteten sich die Kläger, gegen Bezahlung einer Vergütung auf Verlangen der Nebenintervenientin verschiedene Figuren des "Roten Vari" persönlich zu erstellen. Den Klägern wurde für das Jahr 2007 ein Auftragsvolumen von Fr. 240'000.-- garantiert. Der Vertrag galt rückwirkend per 1. Oktober 2006 bis zum Entscheid der Beklagten, das Y._-Konzept nicht weiter zu verwenden bzw. die Zusammenarbeit mit der Nebenintervenientin zu beenden. Zudem sah der Vertrag die Möglichkeit einer Kündigung aus ausserordentlichen Gründen vor. Für das vorliegende Verfahren sind insbesondere die folgenden Bestimmungen des Rahmenvertrags von Bedeutung: "1. T._ beauftragt die Illustratoren gegen Bezahlung einer Entschädigung mit der zeichnerischen Verwirklichung des T._-Konzeptes mittels mehrerer, unterschiedlicher Illustrationen eines oder mehrerer "Roter/n Vari/s" (nachfolgend "Figur/en" genannt). Die Illustratoren nehmen diesen Auftrag an. [...] 16. Ausschliesslichkeit T._ verpflichtet sich, während der Dauer dieses Rahmenvertrages ausschliesslich die Illustratoren mit dem Illustrieren, Korrigieren und Verändern (ausser Farbkorrekturen) der Figur/en für sämtliche Medien zu beauftragen; es sei denn, die Illustratoren können die Aufträge (Briefing) der T._ nicht (vollständig oder teilweise) verwirklichen, oder die Illustratoren haben ihre schriftliche Zustimmung der Auftragserteilung an Dritte erteilt. [... ] 18. Übertragung von Immaterialgüterrechten (Urheberrechte) an den Figuren 18.1. Die Illustratoren übertragen die zu den im Rahmen dieses Vertrags bereits erstellten sowie zukünftig zu erstellenden Figuren inklusive Entwürfe zugehörigen Immaterialgüterrechte, insbesondere Urheberrechte, im Zeitpunkt ihrer Entstehung umfassend und unbefristet auf die T._. 18.2. Die übertragenen Urheberrechte umfassen insbesondere das Recht zur Vervielfältigung und Inverkehrsetzung, Änderung und Bearbeitung der Figuren (gemäss Ziffer 16.) sowie das Recht, diese sog. Verwendungsrechte wiederum auf Dritte zu übertragen. 18.3. Vorstehende Ziffern 18.1 und 18.2 gelten nur unter dem Vorbehalt, dass die T._ den Rahmenvertrag ordnungsgemäss erfüllt hat, und dieser Rahmenvertrag per 31.12.2009 noch in Kraft ist. 19. Verzicht auf Urheberpersönlichkeitsrechte Die Illustratoren verzichten ab dem Zeitpunkt der Entstehung der unter Ziffer 18 genannten Schutzrechte auf deren Geltendmachung; namentlich auf den Anspruch, die Figuren zu veröffentlichen, als Urheber oder Erfinder bezeichnet zu werden oder sich einer Veränderung der Figuren zu widersetzen. Dieser Verzicht ist unbefristet. Die Illustratoren haben jedoch das Recht, die Figuren zu Zwecken der Eigenwerbung frei zu verwenden. [...] 22. Vorbehalten ist die Kündigung dieses Rahmenvertrages sowie der Aufträge (Briefing) aus ausserordentlichen Gründen ohne Berücksichtigung einer Frist oder eines Termins. Ausserordentliche Gründe liegen vor, wenn die Fortführung des Vertragsverhältnisses für eine der beiden Parteien unzumutbar ist, insbesondere wenn a) die Figuren wiederholt zu spät abliefert, b) die Figuren nicht den zwischen den Parteien vereinbarten Anforderungen entsprechen c) T._ wiederholt ihren Zahlungspflichten trotz Mahnung seitens der Illustratoren unter Ansetzung einer Nachfrist von 10 Tagen nicht oder nicht vollständig nachkommt, obwohl die Illustratoren ihre vertraglichen Pflichten ordnungsgemäss erfüllt haben. Die Kündigung aus ausserordentlichen Gründen hat per eingeschriebener Brief zu erfolgen." In Ziffer 15.1.1 des Rahmenvertrags verpflichtete sich die Nebenintervenientin, die Übertragung der Immaterialgüterrechte mit 10 % der während der Jahre 2007, 2008 und 2009 an die Kläger bezahlten Vergütung abzugelten. In Ziffer 15.1.2 wurde die Vergütung für die zu zeichnenden Figuren geregelt. Bis zum 27. April 2009 wurden den Klägern Vergütungen und Abgeltungen in der Höhe von Fr. 361'533.30 überwiesen. Die Nebenintervenientin schloss mit der Beklagten am 28. Juni/4. Juli 2007 ihrerseits eine Vereinbarung ab, worin sie als "Inhaberin des Urheberrechts an der Figur "Roter Vari" der Beklagten die Nutzungsrechte an den Illustrationen "Roter Vari" und an allen in diesem Zusammenhang entwickelten Figuren übertrug. Ziffer 7 dieser Vereinbarung lautet wie folgt: 7. Die Nutzung umfasst das Recht von X._, die Illustration 'roter Vari' und alle in diesem Zusammenhang entwickelten Figuren für den vorbestimmten Zweck (siehe Ziffer 1) unbeschränkt zu vervielfältigen und zu verbreiten. Weitere Verwendungen sowie allfällige Änderungen der Figur 'roter Vari' und aller in diesem Zusammenhang entwickelten Figuren sind nach Absprache mit T._ möglich, wobei X._ den Charakter der Figur 'Roter Vari' und alle in diesem Zusammenhang entwickelten Figuren grundsätzlich unberührt lässt. Zwecks Präsentation des Y._-Programms im Internet zog die Beklagte die W._ AG bei, der sie aufgrund eines Zusammenarbeitsvertrags aus dem Jahre 2002 konkrete Aufträge für den Betrieb der Webseiten des Y._-Programms erteilte. Daneben wurde seitens der Beklagten auch die V._ Werbeagentur AG beauftragt, bestimmte Teile des Y._-Programms zu verwirklichen. Die V._ Werbeagentur AG zog wiederum die U._ AG bei, um Werbefilme zu realisieren. In der Folge kam es zwischen den Klägern und der Nebenintervenientin zu Meinungsverschiedenheiten hinsichtlich der Änderungs- und Bearbeitungsrechte der Kläger gemäss Ziffer 16 des Rahmenvertrags und der Qualität der insbesondere von W._ AG für das Internet bearbeiteten Illustrationen. In zwei E-Mails vom 5. November und 18. Dezember 2007 warfen die Kläger der Nebenintervenientin vor, auf der Y._-Webseite würden vertragswidrige Illustrationen des "Roten Vari" publiziert. Sie wiesen darauf hin, dass nur sie selbst Illustrationen des "Roten Vari" zeichnen, verändern und ergänzen dürften, was an der Sitzung vom 20. Juni 2007 auch den Mitarbeitern von W._ AG mitgeteilt worden sei. Zudem entspreche die Qualität der Arbeit von W._ AG nicht den Mindestanforderungen hinsichtlich Zeichnung, Bild- und Farbkombination und Animation. Der Gesamteindruck bewege sich "zwischen laienhaft und peinlich". Die von ihnen früher verlangten Änderungen/Korrekturen seien nur zum Teil umgesetzt worden; sämtliche vertragswidrige Illustrationen müssten durch von ihnen korrigierte Illustrationen ersetzt werden. Mit Schreiben vom 31. Dezember 2007 verfochten die Kläger erneut ihren Standpunkt, dass die Figur des "Roten Vari" inklusive Kleider, Kostüme und Requisiten nur durch sie gezeichnet werden dürfe. Sie übermittelten der Nebenintervenientin von W._ AG hergestellte Illustrationen, die sie als vertragswidrig einstuften. Sie bemängelten, dass W._ AG trotz der Sitzung vom 20. Juni 2007 vertragswidrig weiter produziere. Auch seien die von ihnen angefertigten Korrekturen für die vor dem 20. Juni 2007 bereits hergestellten Animationen noch nicht vollständig ausgeführt worden. Am 23. Januar 2008 verfasste die Nebenintervenientin ein sog. Factsheet, worin sie zuhanden ihrer Lieferanten und Partner unter "Do's/Don'ts" folgende Anweisung erliess: "Der 'Rote Vari' darf auf fremdgezeichnete Hintergründe gesetzt und mit anderen IIlustrationsstilen kombiniert werden, sofern der 'Rote Vari' nicht verändert wird. Der 'Rote Vari' darf nicht ohne die Freigabe durch Z._ Kommunikation bzw. die Illustratoren ergänzt oder verändert werden. Änderungen oder das Zusammenfügen zweier Illustrationen zu einer neuen Vari-Illustration müssen den Illustratoren in Auftrag gegeben werden. Die Änderungen werden von den Illustratoren nach Stundenaufwand abgerechnet. Ergänzungen am 'Roten Vari' (Kleider, Mütze, Schweisstropfen, Gläser, Wanderstab etc.), die das Wesen / den Charakter der Figur verändern, müssen von den Illustratoren realisiert werden. In Ausnahmen können Ergänzungen in Absprache mit Z._ Kommunikation gewährt werden. Solche 'selbst' realisierten Änderungen müssen jedoch zwingend von Z._ Kommunikation bzw. den Illustratoren abgesegnet werden. Illustrationen, welche den Hintergrund nicht berühren (Hintergrund, Pflanzen etc.) müssen nicht zwingend von den Illustratoren realisiert werden. Sollten vom Stil her aber unbedingt passen. [...]" Mit Schreiben vom 24. April 2008 teilten die Kläger der Nebenintervenientin mit, unzählige - mehrfach erfolglos abgemahnte - Beispiele belegten, dass sie (die Nebenintervenientin) insbesondere ihrer Ausschliesslichkeitsverpflichtung gemäss Ziffer 16 des Rahmenvertragsnicht nachkomme. Sie werde daher aufgefordert, unverzüglich dafür zu sorgen, dass jegliche Verletzung durch sie selbst und durch Unterbeauftragte wie W._ AG und die V._ Werbeagentur AG unterlassen werde. In einem Schreiben vom 17. Februar 2009 warfen die Kläger der Nebenintervenientin weiterhin eine Verletzung der Ausschliesslichkeitsverpflichtung gemäss Ziffer 16 des Rahmenvertrags vor. Sie machten geltend, obwohl die Nebenintervenientin die Kläger am 3. Juni 2008 beauftragt habe, die vertragswidrigen grafischen Darstellungen auf der Website www.y._.ch zu korrigieren und dieser Auftrag ausgeführt und bezahlt worden sei, befinde sich weiterhin der vertragswidrige Content im Netz. Zudem seien in der Beilage weitere 30 vertragswidrige grafische Darstellungen enthalten, die in Werbemitteln verschiedenster Art und auf diversen, von der Beklagten vertriebenen Produkten zu finden seien. Damit verstosse die Nebenintervenientin nicht nur gegen ihre Pflichten aus dem Rahmenvertrag, sondern gefährde zudem das berufliche Ansehen der Kläger, da die vertragswidrigen, durch Dritte erstellten Designs unprofessionell und zum Teil dilettantisch wirkten, was von Dritten den Klägern zugerechnet werde. Dieser Zustand sei trotz mehrmaliger Intervention nicht behoben worden und für die Kläger unzumutbar, weshalb eine letzte Frist bis 10. März 2009 gesetzt werde, um den vertragsgemässen Zustand wiederherzustellen (Entfernung sämtlicher vertragswidriger Designs vom Markt und aus Publikationsmitteln, Einhaltung der Verpflichtung gemäss Rahmenvertrag für neue Designs), widrigenfalls der Vertrag ohne weitere Vorwarnung gemäss Ziff. 22 des Rahmenvertrags fristlos gekündigt werde. Mit Schreiben vom 9. März 2009 wies die Nebenintervenientin den Vorwurf der Vertragsverletzung von sich mit der Begründung, in den ihr zugesandten Beispielen seien keine wesentlichen Veränderungen des "Roten Vari" zu erblicken. Mit Schreiben vom 12. März 2009 kündigten die Kläger das Vertragsverhältnis mit der Nebenintervenientin mit sofortiger Wirkung aufgrund mehrfacher, schwerwiegender und anhaltender Verletzungen des Rahmenvertrags. Auch hätten die Kläger festgestellt, dass zwischenzeitlich weitere Verletzungen stattgefunden hätten, insbesondere bezüglich neu in den Ladengeschäften der Beklagten erhältlichen Waren und Verpackungen. Die Kläger wiesen darauf hin, als Folge der Kündigung würden die Urheberrechte an den von ihnen geschaffenen Werken gemäss Ziffer 18.3 des Rahmenvertrags per sofort an sie zurückfallen. Sämtliche von ihnen unter dem Rahmenvertrag geschaffenen Werke seien bis 6. April 2009 von sämtlichen Publikations- und Werbemitteln, Waren und Warenverpackungen und Websites zu entfernen, widrigenfalls die Rechte der Kläger gegen die Nebenintervenientin und gegen Dritte, insbesondere die Beklagte, auf dem Gerichtswege durchgesetzt würden. Mit Schreiben vom 17. April 2009 orientierten die Kläger die Beklagte über die Kündigung des Rahmenvertrags und hielten fest, sämtliche Unter-Nutzungsrechte der Beklagten an den Werken der Y._-Produktelinie seien dahingefallen, weshalb die Beklagte die Verwendung der Werke bis 30. April 2009 einzustellen habe. Am 21. Dezember 2010 teilte die Nebenintervenientin den Klägern mit, die Beklagte habe im Nachgang zur Referentenaudienz vom 27. September 2010 per 28. September 2010 die Zusammenarbeit mit ihr bezüglich des T._-Konzepts beendet. Damit werde der Rahmenvertrag vom 15./20. Juni 2007 ebenfalls auf diesen Zeitpunkt beendet. Es ist unbestritten, dass die Beklagte den "Roten Vari" auf diversen Produkten und Verpackungen im "Food"-, "Near Food"- und "Non Food"-Bereich verwendet und die weiteren im Rechtsbegehren aufgeführten Figuren für die Kennzeichnung ihres "Krokodils-Snacks" und ihrer Teigwaren "Zoo-Pasta" einsetzt. Zudem verwendet die Beklagte den "Roten Vari" zu Werbezwecken, insbesondere in ihren Restaurants, im Internet und im Newsletter "Y._". B. Am 16. Februar 2010 reichten die Kläger beim Obergericht des Kantons Zürich gegen die X._ Genossenschaft Klage ein mit folgendem Rechtsbegehren: "1. Es sei der Beklagten, unter Androhung der gesetzlichen Folgen von Art. 292 StGB an ihre Organe im Widerhandlungsfall, zu verbieten, ohne schriftliche Zustimmung der Kläger die Figuren Abb. a zu verwenden, insbesondere keinerlei Produkte, Verpackungen, Werbematerialien, Websites, insbesondere www.x._.ch, www.x.x_.ch und www.y._.ch, jeglicher Art, auf oder in welchen eine oder mehrere der Figuren Abb. a - g angebracht resp. enthalten sind, herzustellen, zu benutzen, anzupreisen, anzubieten, zu verkaufen oder sonstwie in Verkehr zu bringen oder bei entsprechenden Handlungen Dritter in irgendeiner Weise mitzuwirken; 2. Es sei die Beklagte, unter Androhung der gesetzlichen Folgen von Art. 292 StGB an ihre Organe im Widerhandlungsfall, zu verpflichten, alle sich im Besitze der Beklagten befindlichen Produkte, Verpackungen, Werbematerialien und Dekorationsartikel, auf oder in welchen eine oder mehrere der im Rechtsbegehren 1 genannten Figuren (Abb. a - g) angebracht resp. enthalten sind, den Klägern zur Vernichtung herauszugeben oder vernichten zu lassen; 3. Es sei die Beklagte, unter Androhung der gesetzlichen Folgen von Art. 292 StGB an ihre Organe im Widerhandlungsfall, zu verpflichten, die im Rechtsbegehren 1 genannten Figuren (Abb. a - g) von allen Datenträgern und Websites der Beklagten, in Bezug auf letztere insbesondere von www.x._.ch, www.x.x_.ch und www.y._.ch, sowie von Einträgen der Beklagten auf Websites von Dritten, insbesondere www.facebook.com, zu entfernen; 4. Es sei die Beklagte, unter Androhung der gesetzlichen Folgen von Art. 292 StGB an ihre Organe im Widerhandlungsfall, zu verpflichten, sämtliche Markenregistrierungen, insbesondere die schweizerische Wort-/Bildmarke Nr. sss, Designhinterlegungen oder sonstige Registrierungen gewerblicher Schutzrechte, in resp. auf welchen eine oder mehrere der im Rechtsbegehren 1 genannten Figuren (Abb. a - g) abgebildet sind oder sonstwie erscheinen, zu löschen resp. löschen zu lassen; 5. Die Beklagte sei, unter Androhung der gesetzlichen Folgen von Art. 292 StGB an ihre Organe im Widerhandlungsfall, zu verpflichten, den Klägern zum Zwecke der Feststellung des ihnen durch die Verwendung der im Rechtsbegehren 1 genannten Figuren (Abb. a - g) entstandenen Schadens und/oder der von der Beklagten unrechtmässig erzielten Erträge und Gewinne vorab folgende Auskünfte zu erteilen: - Darlegung des Umfangs der Benutzung der im Rechtsbegehren 1 genannten Figuren (Abb. a - g), insbesondere im Zusammenhang mit der Produktelinie "Y._", unter Lieferung aller relevanten Angaben, insbesondere Auflistung sämtlicher Aktivitäten im Zusammenhang mit der Herstellung und dem Vertrieb von Produkten sowie der Werbung für Produkte und Dienstleistungen, auf resp. in denen die im Rechtsbegehren 1 genannten Figuren (Abb. a - g) verwendet wurden, - Rechnungslegung über die mit der Herstellung, dem Verkauf, Vertrieb oder sonstigen Inverkehr-Bringung sämtlicher Produkte und Dienstleistungen unter Verwendung der im Rechtsbegehren 1 genannten Figuren (Abb. a - g) seit 10. April 2007 erzielten Erträge und Gewinne vor Gemeinkosten unter Lieferung aller relevanten Angaben, insbesondere Vorlage von Bilanz- und Ertragsrechnung ab dem Geschäftsjahr 2007, Buchhaltungsbelegen, Auftragsbestätigungen, Lieferscheinen und Rechnungen, - Darlegung des Umfangs der vertraglichen Beziehung mit der Z._ Kommunikation AG resp. jeglichen Dritten, die mit der grafischen Darstellung, Umsetzung oder Veränderung eine oder mehrere der im Rechtsbegehren 1 genannten Figuren (Abb. a - g) beauftragt wurden, unter Lieferung aller relevanten Angaben, insbesondere Verträge, Korrespondenzen, Protokolle und Rechnungen, - Nennung aller Registrierungen und Anmeldungen von Marken, Designs oder sonstigen gewerblichen Schutzrechten, in resp. auf welchen eine oder mehrere der im Rechtsbegehren genannten Figuren (Abb. a - g) abgebildet sind oder sonstwie erscheinen, unter Lieferung aller relevanten Angaben, insbesondere Registrierungs- und Anmeldebelege; 6. Die Beklagte sei - gemäss der nach Durchführung des Beweisverfahrens zu treffenden Wahl der Kläger - zu verpflichten, den Klägern a) entweder den Schaden, zu ersetzen, welcher den Klägern aus der unrechtmässigen Benutzung der im Rechtsbegehren 1 genannten Figuren (Abb. a - g) durch die Beklagte seit spätestens 20. April 2009 entstanden ist, zuzüglich Zins von 5% p.a. seit Schadenseintritt; oder b) den Gewinn herauszugeben, den die Beklagte aus der unrechtmässigen Benutzung der im Rechtsbegehren 1 genannten Figuren (Abb. a - g) seit spätestens 20. April 2009 erzielt hat, zuzüglich Zins von 5% p.a. seit Gewinnanfall; 7. Die Kläger seien zu ermächtigen, das Urteilsdispositiv in richterlich zu bestimmenden Publikationsorganen und in richterlich zu bestimmender Grösse auf Kosten der Beklagten zu veröffentlichen". Die Beklagte schloss auf Abweisung der Klage und verkündete der Z._ Kommunikation AG den Streit. Mit Eingabe vom 18. Mai 2010 trat diese als Nebenintervenientin auf Seiten der Beklagten dem Prozess bei. Mit Urteil vom 27. April 2012 wies das Obergericht die Klage ab. C. Die Beschwerdeführer beantragen mit Beschwerde in Zivilsachen, das Urteil des Obergerichts vom 27. August 2012 aufzuheben und die Klagebegehren gutzuheissen. Eventualiter sei die Sache zur Berichtigung/Ergänzung des Sachverhalts und Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Nebenintervenientin liess sich nicht vernehmen. Die Vorinstanz verzichtete auf eine Vernehmlassung. Die Beschwerdeführer reichten eine Replik ein. Die Beschwerdegegnerin verzichtete auf Gegenbemerkungen. 