Sachverhalt:
A. Vom 20. November bis 9. Dezember 2009 legte der Gemeinderat Muhen ein Baugesuch von Y._ für die Umnutzung und Erweiterung des bestehenden Pferdestalls in eine Ferienpension für Hunde, Katzen und Kleintiere auf der Parzelle Nr. 2264 in Muhen öffentlich auf. Gegen das in der Landwirtschaftszone gelegene Vorhaben erhoben unter anderen A._, A.B._ und B.B._ sowie A.C._ und B.C._ Einsprache.
Das kantonale Departement für Bau, Verkehr und Umwelt (BVU) stimmte dem Bauvorhaben am 25. Januar 2010 unter Auflagen zu. Am 12. Juli 2010 erteilte der Gemeinderat Muhen die Baubewilligung unter Bedingungen und Auflagen. Die erwähnten Einsprachen wies er im Wesentlichen ab, soweit er darauf eintrat. Eine gegen diesen Entscheid gerichtete Verwaltungsbeschwerde der unterlegenen Einsprecher wies der Regierungsrat des Kantons Aargau am 16. Februar 2011 ab. In einer gegen diesen Entscheid gerichteten Verwaltungsgerichtsbeschwerde verlangten A._, A.B._ und B.B._ sowie A.C._ und B.C._ die Aufhebung des Entscheids des Regierungsrats vom 16. Februar 2011. Das Verwaltungsgericht des Kantons Aargau wies die Beschwerde mit Urteil vom 27. April 2012 ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten und subsidiärer Verfassungsbeschwerde vom 15. Juni 2012 an das Bundesgericht beantragen A._, A.B._ und B.B._ sowie A.C._ und B.C._, das Urteil des Verwaltungsgerichts vom 27. April 2012 sei aufzuheben und die Baubewilligung für das Vorhaben zu verweigern.
C. Das Verwaltungsgericht stellt den Antrag, auf die Beschwerde sei nicht einzutreten, da sie im Wesentlichen die beim Verwaltungsgericht eingereichte Beschwerde wiederhole und keine Auseinandersetzung mit dem angefochtenen Entscheid enthalte; falls darauf eingetreten werde, sei die Beschwerde abzuweisen. Y._ und der Gemeinderat Muhen beantragen, die Beschwerde in öffentlich-rechtlichen Angelegenheiten sei abzuweisen, soweit darauf einzutreten sei; auf die subsidiäre Verfassungsbeschwerde sei nicht einzutreten.
Das Bundesamt für Umwelt (BAFU) gelangt zum Schluss, dass das Urteil des Verwaltungsgerichts mit der Umweltschutzgesetzgebung des Bundes vereinbar sei. Das Bundesamt für Raumentwicklung (ARE) verzichtet auf eine Stellungnahme zur Beschwerde.
In einer weiteren Eingabe vom 17. Dezember 2012 beziehen sich die Beschwerdeführer auf das Urteil des Bundesgerichts 1C_510/2011 vom 18. April 2012. Sie ergänzen ihre Rechtsbegehren mit dem Antrag, die Sache sei eventuell an die Vorinstanz zur Prüfung nach der neuesten Bundesgerichtspraxis zurückzuweisen. Der Gemeinderat Muhen bestreitet, dass es sich um eine neue Rechtsprechung handle und weist darauf hin, dass sich der Sachverhalt des Urteils 1C_510/2011 vom 18. April 2012 von der vorliegenden Angelegenheit erheblich unterscheide.

Erwägungen:
1. Das angefochtene Urteil des Verwaltungsgerichts ist ein Entscheid einer letzten kantonalen Instanz (<ref-law>). Ihm liegt ein Beschwerdeverfahren zu einer bewilligungspflichtigen Anlage ausserhalb der Bauzone und damit eine öffentlich-rechtliche Angelegenheit zu Grunde. Das Bundesgerichtsgesetz enthält auf dem Gebiet des Bau- und Planungsrechts keinen Ausschlussgrund von der Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 lit. a und Art. 83 BGG). Als Nachbarn, welche auf ihren Grundstücken nach dem Lärmgutachten der Planteam GHS AG vom 4. November 2009 die Lärmimmissionen des geplanten Betriebs wahrnehmen können, sind die Beschwerdeführer durch das angefochtene Urteil besonders berührt und haben ein schützenswertes Interesse an dessen Aufhebung. Entsprechend sind sie zur Beschwerde legitimiert (<ref-law>).
Die weiteren Sachurteilsvoraussetzungen der Beschwerde in öffentlich-rechtlichen Angelegenheiten geben zu keinen Bemerkungen Anlass. Auf die fristgerecht eingereichte Beschwerde ist einzutreten. Indessen bleibt für die subsidiäre Verfassungsbeschwerde kein Raum, weshalb darauf nicht eingetreten werden kann.
2. 2.1 Die Beschwerdegegnerin beabsichtigt die Umnutzung und Erweiterung des auf der Parzelle Nr. 2264 bestehenden Pferdestalls in eine Ferienpension für maximal 37 Hunde, ca. 40 Katzen und bis zu 20 Kleinsäuger. Das bestehende Gebäude umfasst ein Wohnhaus mit angebauter Scheune. Der Ökonomieteil soll umgebaut werden. Für die Hundehaltung ist auf der Nordseite ein 10 m x 22.3 m grosser Anbau mit 13 Hundeboxen geplant. Vor den Hundeboxen sind Aussenzwinger vorgesehen. Die Aussenzwinger werden mit einer Lärmschutzwand vom übrigen Areal abgetrennt. Im Nordwesten der Parzelle sowie auf der westlichen Seite der Aussenzwinger sollen Ausläufe für die Hunde eingerichtet werden. Die Hunde können sich von 8.00 - 12.00 Uhr sowie von 14.00 - 18.00 Uhr im Freien aufhalten.
Die Parzelle Nr. 2264 befindet sich gemäss Kulturlandplan der Gemeinde Muhen vom 13. Juni 1997 in der Landwirtschaftszone L1. Diese ist für die überwiegend bodenabhängige Produktion in den Bereichen Acker- und Futterbau, Tierhaltung, Gemüse-, Obst- und Rebbau sowie für den produzierenden Gartenbau bestimmt (Art. 11 der Bau- und Nutzungsordnung [BNO] vom 13. Juni 1997). Die Zulässigkeit von weiteren Produktionsmethoden und Nutzungsformen richtet sich nach dem eidgenössischen und kantonalen Recht (Art. 11 Abs. 2 BNO).
2.2 Nach Art. 22 Abs. 2 lit. a RPG setzt eine Bewilligung die Zonenkonformität der Baute oder Anlage voraus. Da die fragliche Parzelle in der Landwirtschaftszone L1 liegt, sind nur solche Bauten und Anlagen zonenkonform, die der überwiegend bodenabhängigen Produktion dienen (vgl. Art. 16a RPG i.V.m. Art. 11 BNO). Das umstrittene Tierheim dient nicht der bodenabhängigen Produktion, was eine ordentliche Baubewilligung ausschliesst.
2.3 Nach Art. 24 RPG können im Sinne einer Ausnahme Bewilligungen zur Errichtung von Bauten und Anlagen oder zu deren Zweckänderung erteilt werden, wenn der Zweck einen Standort ausserhalb der Bauzonen erfordert und keine überwiegenden Interessen entgegenstehen. Die Standortgebundenheit im Sinne von Art. 24 lit. a RPG ist nach ständiger bundesgerichtlicher Praxis zu bejahen, wenn eine Anlage aus technischen oder betriebswirtschaftlichen Gründen oder wegen der Bodenbeschaffenheit auf einen Standort ausserhalb der Bauzone angewiesen ist, oder wenn ein Werk aus bestimmten Gründen in einer Bauzone ausgeschlossen ist (vgl. <ref-ruling> E. 3.1 S. 68; <ref-ruling> E. 4a S. 255; <ref-ruling> E. 5a S. 261; BERNHARD WALDMANN/PETER HÄNNI, Raumplanungsgesetz, Kommentar, 2006, Rz. 8 ff. zu Art. 24 RPG). Dabei genügt eine relative Standortgebundenheit: Es ist nicht erforderlich, dass überhaupt kein anderer Standort in Betracht fällt; es müssen jedoch besonders wichtige und objektive Gründe vorliegen, die den vorgesehenen Standort gegenüber anderen Standorten innerhalb der Bauzone als viel vorteilhafter erscheinen lassen (<ref-ruling> E. 4.2 S. 417; <ref-ruling> E. 4a S. 362; Urteil des Bundesgerichts 1C_551/2010 vom 7. Dezember 2011; WALTER HALLER/PETER KARLEN, Raumplanungs-, Bau- und Umweltrecht, 3. Aufl., Band I, 1999 S. 195 Rz. 711; WALDMANN/HÄNNI, a.a.O., Rz. 10 zu Art. 24).
2.4 Die Vorinstanzen bejahen die Standortgebundenheit und damit die Bewilligungsfähigkeit des Vorhabens. Die Immissionen, die das Tierheim verursachen werde, übersteige das für eine Bauzone zumutbare Mass. Sie stützen sich dabei auf eine Rechtsprechung des Bundesgerichts, wonach ein Bauvorhaben "negativ" standortgebunden sein könne, wenn es wegen seiner Immissionen in der Bauzone ausgeschlossen sei oder nicht sinnvoll betrieben werden könne.
2.4.1 Die Frage nach der negativen Standortgebundenheit kann sich erst stellen, wenn für ein Bauvorhaben in der Region keine geeignete Nutzungszone zur Verfügung steht (<ref-ruling> E. 2d S. 21, WALDMANN/HÄNNI, a.a.O., Rz. 10 zu Art. 24; HALLER/KARLEN, a.a.O., S. 196 Rz. 712). Vor der Bejahung einer negativen Standortgebundenheit ist deshalb die Eignung von Bauzonen in einem weiteren regionalen Umfeld zu prüfen (RUDOLF MUGGLI, in: Kommentar RPG, 2009, Rz. 12 zu Art. 24 RPG).
2.4.2 Die Vorinstanzen verzichteten auf die Prüfung, ob das umstrittene Tierheim in einer Bauzone oder Speziallandwirtschaftszone in der Umgebung des umstrittenen Standorts errichtet werden könnte. Das Verwaltungsgericht stützt sich im angefochtenen Entscheid im Wesentlichen auf zwei Urteile des Bundesgerichts, in welchen der Betrieb von Tierheimen ausserhalb der Bauzonen wegen ihrer Immissionsträchtigkeit grundsätzlich als negativ standortgebunden bezeichnet wurde (vgl. Urteil 1A.263/1992 vom 5. April 1994 in: ZBI 96/1995, S. 166 f. E. 2c; Urteil 1A.185/1988 vom 16. Juni 1989 in: ZBl 91/1990, S. 187 ff. E. 5b). Im letztgenannten Urteil ging es um die Haltung von 60 Schlittenhunden, die wegen entgegenstehender Interessen nicht bewilligt werden konnte (ZBI 91/1990, S. 187 ff.). Das Verwaltungsgericht bezieht sich auf allgemeine Erwägungen des Bundesgerichts in den genannten Urteilen, wonach das unvermeidliche Gebell der Hunde und allenfalls auch die mit dieser Art der Tierhaltung verbundene Geruchsbelästigung in einer Wohn-, Gewerbe- oder Industriezone für die Nachbarn in der Regel unzumutbar seien. In einem Fall habe das Bundesgericht zusätzlich darauf hingewiesen, dass im Kanton Aargau alle Tierheime in der Landwirtschaftszone lägen und sich für das damalige Bauvorhaben in den Bauzonen der Standortgemeinde oder einer benachbarten Gemeinde kein geeigneter Standort finden lasse (ZBI 96/1995, S. 167 E. 5c). Es bestehe kein Anlass von dieser konstanten Rechtsprechung abzuweichen.
2.4.3 Weder den Akten noch dem angefochtenen Entscheid lässt sich entnehmen, inwiefern in der vorliegenden Angelegenheit nach möglichen Standorten im regionalen Umfeld in einer geeigneten Nutzungszone oder an einer besser geeigneten Stelle ausserhalb der Bauzonen gesucht wurde. Aus der Stellungnahme vom 3. Dezember 2009 des Departements Finanzen und Ressourcen, Abteilung Landwirtschaft, ergibt sich, dass sich der Standort der Baute und der Auslaufflächen (insgesamt rund 40 Aren) auf Fruchtfolgeflächen der Güteklasse 1 befindet. Es handle sich bei der betreffenden Fläche jedoch um eine bestehende Gebäudeparzelle, die wegen der bisherigen Pferdehaltung bereits heute nicht landwirtschaftlichen Zwecken diene. Durch die vorgesehene Umnutzung würden somit die landwirtschaftlichen Freihalteinteressen nicht stärker tangiert.
Die genannten Ausführungen lassen ausser Acht, dass mit dem umstrittenen Bauvorhaben zusätzlich zum Umbau der bisherigen Stallungen ein neuer Anbau für die Unterbringung der 37 Hunde auf einer Fläche von rund 220 m2 und zusätzlich 13 neue Aussenzwinger auf einer Fläche von rund 234 m2 geplant sind. Auf der verbleibenden Grundstücksfläche sind überwiegend umzäunte Auslaufgehege für die aufgenommenen Tiere vorgesehen. Damit soll das als Fruchtfolgefläche ausgeschiedene Grundstück weitaus intensiver zu nichtlandwirtschaftlichen Zwecken genutzt werden, als dies mit der früheren Pferdehaltung in den alten Stallungen der Fall war. Eine solche Ausdehnung nichtlandwirtschaftlicher Nutzung von Fruchtfolgeflächen ist mit der Pflicht der Kantone zur dauernden Erhaltung ihrer Fruchtfolgeflächen (<ref-law>; SR 700.1) kaum vereinbar. Im Rahmen der Suche nach Alternativ-Standorten für das Tierheim hätte diesem Umstand Rechnung getragen werden müssen. Falls ein Standort in einer geeigneten Bauzone (E. 2.4.1) nicht vorhanden sein sollte, müsste unter anderem geprüft werden, ob ein Standort auf Land, das nicht zu den hochwertigen Fruchtfolgeflächen gehört oder bereits durch andere immissionsträchtige Anlagen (wie z.B. Hochleistungsstrassen oder Bahnlinien) mit Lärm vorbelastet ist, für die umstrittene Nutzung besser geeignet wäre. Eine solche Prüfung hat nicht stattgefunden. Die Bejahung der Standortgebundenheit des Tierheims ohne ernsthafte Beurteilung möglicher Alternativ-Standorte ist mit Art. 24 lit. a RPG nicht vereinbar.
2.5 Es ergibt sich, dass die Beschwerde gutzuheissen und der angefochtene Entscheid aufzuheben ist, weil die Vorinstanzen die Standortgebundenheit des Tierheims ohne Prüfung von anderen möglichen Standorten bejaht haben. Damit ist der weiteren Frage, ob dem Vorhaben überwiegende Interessen entgegenstehen nicht mehr detailliert nachzugehen. Ob für das Bauvorhaben eine Bewilligung im Sinne von Art. 24c RPG erteilt werden könnte, steht nicht zur Diskussion. Die Vorinstanz hat diese Frage zu Recht nicht behandelt, da das umstrittene Projekt offensichtlich über das nach der genannten Bestimmung zulässige Änderungsmass hinausgeht.
3. Somit ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gutzuheissen und der angefochtene Entscheid des Verwaltungsgerichts aufzuheben. Die Gerichtskosten sind der unterliegenden privaten Beschwerdegegnerin aufzuerlegen (<ref-law>). Diese hat die Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>). Die Kosten des verwaltungsgerichtlichen Verfahrens und des Verfahrens vor dem Regierungsrat sind entsprechend dem Verfahrensausgang ebenfalls der privaten Beschwerdegegnerin aufzuerlegen (<ref-law>). Diese hat überdies die den Beschwerdeführern vor dem Verwaltungsgericht und dem Regierungsrat entstandenen Parteikosten zu ersetzen (<ref-law>). Die Zusprechung einer Parteientschädigung an die Gemeinde Muhen für die vorinstanzlichen Verfahren erscheint angesichts des Verfahrensausgangs nicht gerechtfertigt.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen und das Urteil des Verwaltungsgerichts des Kantons Aargau vom 27. April 2012 aufgehoben.
2. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3. Die Gerichtskosten des bundesgerichtlichen Verfahrens von Fr. 4'000.-- werden der privaten Beschwerdegegnerin auferlegt.
4. Die private Beschwerdegegnerin hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
5. Die Kosten des verwaltungsgerichtlichen Verfahrens von insgesamt Fr. 5'464.-- sowie des Verfahrens vor dem Regierungsrat des Kantons Aargau von insgesamt Fr. 2'033.35 werden der privaten Beschwerdegegnerin auferlegt. Die private Beschwerdegegnerin hat zudem den Beschwerdeführern für das verwaltungsgerichtliche Verfahren und das Verfahren vor dem Regierungsrat eine Parteientschädigung von insgesamt Fr. 10'000.-- (inkl. Auslagen und MWSt) zu bezahlen.
6. Dieses Urteil wird den Parteien, dem Gemeinderat Muhen, dem Regierungsrat des Kantons Aargau, dem Verwaltungsgericht des Kantons Aargau, 3. Kammer, dem Bundesamt für Raumentwicklung und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 17. April 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Haag