Faits: A. C._ exploite un domaine agricole sur le territoire de la Commune de Vuadens. Il est propriétaire de la parcelle 1'119 du registre foncier, un bien-fonds de 60'000 m2 situé en zone agricole. Le 5 mars 2004, le prénommé a requis l'autorisation de construire sur ce terrain une écurie pour trente vaches et huit génisses en stabulation libre, ainsi qu'une fosse à purin de 500 m3. La façade nord du bâtiment projeté aurait une longueur de 35,90 m et une hauteur d'au moins 10 m par rapport au terrain naturel. Il était prévu d'implanter cette construction dans le voisinage immédiat des villas qui bordent la parcelle au nord. Elle serait située à 11,90 m de la parcelle 1'033, propriété de A._ et B._. Ces derniers ont formé opposition contre le projet, en se plaignant de la proximité de l'écurie et des nuisances qui en découleraient. Ils demandaient que le bâtiment soit implanté plus au sud sur la parcelle 1'119. Par arrêt du 19 septembre 2007, le Tribunal administratif du canton de Fribourg, actuellement remplacé par le Tribunal cantonal, a admis le recours formé par les époux A._ et B._ contre l'autorisation de construire le projet litigieux. Il a considéré en substance que l'implantation du nouveau rural à proximité immédiate de la zone à bâtir empêchait toute possibilité de véritable agrandissement et qu'on ne pouvait dès lors pas admettre que cette construction était nécessaire à l'exploitation au sens de l'art. 34 al. 4 let. a de l'ordonnance sur l'aménagement du territoire du 28 juin 2000 (OAT; RS 700.1). De plus, procédant à une pesée des intérêts en présence, les juges cantonaux ont considéré que l'implantation choisie par C._ ne répondait à aucun intérêt digne de protection et qu'elle portait atteinte à divers intérêts publics. La construction litigieuse devait donc être refusée également sur la base de l'art. 34 al. 4 let. b OAT. Le Tribunal fédéral a confirmé ce jugement par arrêt du 11 août 2008 (cause 1C_372/2007). B. Le 23 septembre 2009, C._ a déposé une autorisation de construire une nouvelle installation consistant en une écurie en stabulation libre prévue pour septante têtes de bétail, une fosse à lisier de 500 m3 ainsi qu'un hangar où il pourrait stationner ses engins agricoles, accolé au nord du nouveau rural. Le projet mis à l'enquête se situait 13 m plus au sud que le précédent, soit à une distance de 25 m de la limite du fonds des époux A._ et B._. D'un volume de 11'270 m3, il était également de dimensions plus imposantes, soit 39,60 m de long au nord pour 11,60 m de hauteur au faîte. Les époux A._ et B._ ont formé opposition. La commune et les services consultés ont émis un préavis favorable. En particulier, le service cantonal de l'environnement a constaté que le projet était conforme aux prescriptions en matière olfactives et que les valeurs limites en matière de protection contre le bruit seraient respectées. Par décision du 12 août 2010, la Direction de l'aménagement, de l'environnement et des constructions du canton de Fribourg (ci-après: la DAEC) a octroyé l'autorisation spéciale de construire l'installation projetée. Elle a considéré pour l'essentiel que les exigences posées par l'art. 16a de la loi sur l'aménagement du territoire du 22 juin 1979 (LAT; RS 700) et précisées par l'art. 34 OAT étaient remplies. Le 5 novembre 2010, le Préfet du district de la Gruyère (ci-après: le préfet) a délivré le permis de construire et rejeté les oppositions. C. A._ et B._ ont recouru contre la décision du préfet auprès du Tribunal cantonal. Ils ont également formé un recours contre la décision du 12 août 2010 de la DAEC octroyant l'autorisation spéciale. Par arrêt du 14 novembre 2011, le Tribunal cantonal a rejeté les recours, considérant en substance que le projet litigieux différait singulièrement de l'installation initialement souhaitée mise à l'enquête en 2004 et s'avérait conforme aux prescriptions légales topiques. Du moment que la construction projetée obéissait aux exigences d'une exploitation agricole raisonnable tout en respectant les normes sur la protection de l'environnement, notamment en matière d'immissions de bruits et d'odeurs, il n'y avait pas lieu d'imposer au constructeur le choix d'un autre emplacement pour son rural. La solution retenue ne heurtait au demeurant aucun intérêt prépondérant. D. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent au Tribunal fédéral d'annuler l'arrêt précité ainsi que la décision de la DAEC du 12 août 2010 et celle du préfet du 5 novembre 2010. Les recourants se plaignent d'un établissement inexact des faits et d'une violation de l'art. 34 al. 4 OAT, en relation avec l'art. 16a LAT, et de l'art. 11 al. 2 de la loi fédérale du 7 octobre 1983 sur la protection de l'environnement (LPE; RS 814.01). 