Faits:
A. B.X._ est propriétaire de la parcelle n° 7593 du registre foncier de la commune de Fully sise au lieu-dit "Les Epenays". Ce bien-fonds, d'une superficie de 1'503 m2, supporte un bâtiment rural (grange, écurie, silo) dans la zone de plaine entre Châtaignier et Saxé, accessible par la route de Solverse. Il est classé en zone agricole.
Le 9 mars 2010, B.X._ et son époux, A.X._, ont sollicité l'autorisation de transformer et agrandir le rural. Le projet consistait à ajouter un bâtiment d'habitation de 4 pièces sur un niveau, avec couvert à voitures attenant au rural existant. Ils ont justifié ce projet par le fait qu'ils exploitaient à titre professionnel 5'500 m2 de surface agricole dans le secteur des Epenays, ce qui leur permettait d'accueillir en dehors des périodes d'estivage un cheptel variant entre 14 et 20 unités de gros bétail (UGB; vaches laitières, pièces de gros bétail, génisses et veaux). L'exploitation de ce domaine sans y disposer d'un lieu de séjour créait, selon eux, des inconvénients pratiques majeurs; de plus, B.X._, gravement accidentée en 2003, devait participer à l'exploitation de la ferme familiale pour les besoins de sa santé. Mis à l'enquête publique, le projet n'a suscité aucune opposition.
Dans le cadre de l'instruction, le Service de l'agriculture du canton du Valais (ci-après: le SAgr) a, le 21 mai 2010, préavisé favorablement la demande, relevant qu'il s'agissait d'une exploitation relativement importante gérée de manière autonome depuis plus de 15 ans dans un cadre familial et qui comptait plus d'une unité de main-d'oeuvre standart (UMOS); il a justifié son préavis par le caractère exceptionnel de cette demande, en lien avec la réinsertion sociale d'une personne handicapée pour laquelle le contact avec les animaux était bénéfique. Le 31 mai 2010, le Service du développement territorial (ci-après: le SDT) a préavisé négativement la demande, relevant que le projet n'était pas conforme à la zone agricole.
Le 30 juin 2010, la Commission cantonale des constructions du canton du Valais (ci-après: la CCC) a refusé l'autorisation de construire sollicitée. Le Conseil d'Etat valaisan a confirmé cette décision par arrêt du 28 septembre 2011.
B. Par arrêt du 16 février 2012, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours formé par les époux contre cette décision. En substance, elle a considéré que le projet d'habitation n'était pas indispensable à l'exploitation agricole; il n'était donc pas conforme à l'affectation de la zone agricole au sens de l'art. 16a LAT. De plus, l'implantation de cet ouvrage hors de la zone à bâtir n'était pas imposée par sa destination et ne pouvait ainsi bénéficier de la dérogation prévue par l'art. 24 LAT. Les recourants ne pouvaient en outre se prévaloir du principe de l'égalité de traitement dans l'illégalité. L'instance précédente a, par ailleurs, renoncé à administrer les offres de preuve formulées par les recourants.
C. Agissant par la voie du recours en matière de droit public, les époux X._ demandent au Tribunal fédéral d'annuler l'arrêt entrepris et de renvoyer le dossier à l'instance précédente pour nouvelle décision au sens des considérants.
Le Tribunal cantonal et la CCC renoncent à se déterminer. Le Conseil d'Etat conclut au rejet du recours et se réfère aux considérants de l'arrêt entrepris. La Commune de Fully déclare maintenir ses préavis positifs. Invité à se déterminer, l'Office fédéral du développement territorial n'a pas formulé d'observations.

Considérant en droit:
1. Dirigé contre une décision prise en dernière instance cantonale rendue dans le domaine du droit public de l'aménagement du territoire et des constructions, le recours est recevable comme recours en matière de droit public conformément aux <ref-law>, aucune des exceptions prévues à l'<ref-law> n'étant réalisée. Les recourants ont pris part à la procédure de recours devant l'autorité cantonale et sont particulièrement touchés par l'arrêt attaqué qui confirme le refus de l'autorisation de construire qu'ils ont sollicitée. Ils peuvent ainsi se prévaloir d'un intérêt personnel et digne de protection à l'annulation de l'arrêt attaqué. Ils ont donc la qualité pour agir au sens de l'<ref-law>. Les autres conditions de recevabilité du recours en matière de droit public étant remplies, il convient d'entrer en matière.
2. A l'appui de leur recours, les intéressés demandent au Tribunal fédéral d'administrer divers moyens de preuve. Leur requête tendant à l'édition du dossier complet de la cause est satisfaite, le Tribunal cantonal et le Conseil d'Etat ayant déposé leur dossier dans le délai qui leur avait été imparti à cette fin (cf. <ref-law>); le dossier du Conseil d'Etat est composé de ceux de la Commune et de la CCC, ce dernier comprenant entre autres le préavis du 21 mai 2010 du SAgr. Il n'y a par ailleurs pas lieu de donner suite à la requête d'inspection locale, le Tribunal fédéral s'estimant suffisamment renseigné pour statuer en l'état du dossier; au demeurant, les recourants n'expliquent pas en quoi celle-ci se révélerait nécessaire. Doivent également être écartées pour les motifs invoqués ci-après (cf. consid. 3.2 et 5.2), leurs requêtes de preuve tendant à l'émission d'une expertise et d'un second préavis du SAgr au sujet du caractère agricole de l'exploitation et de la nécessité pour les exploitants, du point de vue d'une exploitation agricole rationnelle, de résider sur place. Il en va de même de leur demande d'édition de dossiers relatifs à des cas prétendument similaires au leur (cf. consid. 6).
3. Dans un grief formel qu'il convient d'examiner en premier lieu, les recourants se plaignent d'une violation du droit d'être entendu garanti à l'art. 29 al. 2 Cst. Ils reprochent aux instances précédentes d'avoir rejeté leur réquisition de preuve tendant à ce que le SAgr émette un nouveau préavis concernant le caractère agricole de leur exploitation et la nécessité pour les exploitants de résider sur place.
3.1 Tel qu'il est reconnu par cette disposition, le droit d'être entendu comprend notamment le droit pour l'intéressé de prendre connaissance du dossier, d'offrir des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 5.1 p. 293; <ref-ruling> consid. 2.2 p. 504 s.). Toutefois, le droit d'être entendu ne peut être exercé que sur les éléments qui sont déterminants pour décider de l'issue du litige. Il est ainsi possible de renoncer à l'administration de certaines preuves offertes, lorsque le fait dont les parties veulent rapporter l'authenticité n'est pas important pour la solution du cas, lorsque les preuves résultent déjà de constatations versées au dossier ou lorsque le juge parvient à la conclusion qu'elles ne sont pas décisives pour la solution du litige ou qu'elles ne pourraient l'amener à modifier son opinion. Ce refus d'instruire ne viole le droit d'être entendu des parties que si l'appréciation anticipée de la pertinence du moyen de preuve offert, à laquelle le juge a ainsi procédé, est entachée d'arbitraire (<ref-ruling> consid. 5.3 p. 236; <ref-ruling> consid. 3 p. 157; <ref-ruling> consid. 6c/cc in fine p. 135).
L'arbitraire, prohibé par l'art. 9 Cst., ne résulte pas du seul fait qu'une autre solution pourrait entrer en considération ou même qu'elle serait préférable; le Tribunal fédéral ne s'écarte de la solution retenue en dernière instance cantonale que si elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté ou si elle heurte de manière choquante le sentiment de la justice ou de l'équité. Il ne suffit pas que la motivation de la décision soit insoutenable; encore faut-il qu'elle soit arbitraire dans son résultat (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 2.2.2 p. 318 s. et les références). Il appartient au recourant de démontrer le caractère arbitraire par une argumentation répondant aux exigences de l'<ref-law>, respectivement de l'<ref-law> (<ref-ruling> consid. 4.1.2 p. 62).
3.2 En l'espèce, le Tribunal cantonal ayant procédé à l'examen anticipé du moyen de preuve demandé par les recourants, ces derniers devaient démontrer, conformément aux exigences accrues de motivation rappelées ci-dessus, en quoi cette appréciation ayant conduit à refuser d'ordonner un second préavis du SAgr serait arbitraire. Or, les recourants se contentent d'affirmer qu'en renonçant à un nouveau préavis, l'instance précédente aurait refusé de reconnaître qu'il était nécessaire pour les époux exploitants de résider sur le lieu de leur exploitation. Leur argumentation se réduit à l'affirmation que les faits pertinents sont de savoir si, compte tenu de la législation actuelle (LPA, RS 455; OPD, RS 910.13) et, pour des raisons de rationalisation, il est nécessaire pour eux de résider au centre de leur domaine. Ils ne font que substituer leur appréciation à celle de l'instance précédente, sans critiquer les motifs retenus par celle-ci. Ils n'exposent en particulier pas pour quelle raison le préavis du SAgr aurait dû l'emporter sur celui du SDT qui a estimé que le projet litigieux n'était pas conforme à la zone agricole. En se bornant à opposer leur propre appréciation à celle du Tribunal cantonal, leur argumentation ne répond pas aux exigences accrues de motivation découlant des art. 42 al. 2 et 106 al. 2 LTF, de sorte que leur critique est irrecevable (cf. <ref-ruling> consid. 8.1 p. 153).
4. Les recourants se plaignent d'une constatation partiellement inexacte et incomplète des faits pertinents.
4.1 Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>), sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente, il doit expliquer de manière circonstanciée en quoi les conditions de l'<ref-law> seraient réalisées et la correction du vice susceptible d'influer sur le sort de la cause (<ref-law>; <ref-ruling> consid 5.2.2 p. 322 s.). A défaut, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué. En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (<ref-ruling> consid. 5.1 p. 356 et les arrêts cités).
4.2 Les recourants font grief au Tribunal cantonal de mentionner que le projet prévoyait la construction d'"une villa"; il s'agissait en réalité d'un "rural, c'est-à-dire une maison d'habitation pour paysans". lls n'expliquent toutefois pas en quoi cette constatation serait constitutive d'arbitraire. Au demeurant, cet élément apparaît sans incidence sur l'issue du litige puisque ce n'est pas tant le caractère de l'habitation que le principe même de son implantation en zone agricole qui est contesté (cf. consid. 5).
Les recourants reprochent également à l'autorité cantonale d'avoir retenu qu'ils "exploitaient à titre professionnel 5'500 m2 de surfaces agricoles dans le secteur des Epenays" au lieu de 15 hectares. Ils ne se réfèrent toutefois à aucune pièce du dossier, hormis leur recours cantonal, et se contentent à cet égard d'affirmer que ces éléments de fait n'ont pas été contestés par les instances précédentes. Dans ces circonstances, il n'y a pas lieu de corriger ou compléter les faits retenus dans l'arrêt attaqué. Le Tribunal fédéral est par conséquent lié par ceux-ci conformément à l'<ref-law> et le grief doit être écarté.
5. Les recourants se plaignent d'une violation des art. 16a et 22 LAT, ainsi que de l'art. 34 al. 4 de l'ordonnance du 28 juin 2000 sur l'aménagement du territoire (OAT, RS 700.1). Selon eux, leur projet d'habitation serait conforme à la zone agricole.
5.1 En vertu de l'art. 16a al. 1 LAT, sont conformes à l'affectation de la zone agricole les constructions qui sont nécessaires à l'exploitation agricole. A cet égard, l'<ref-law> précise que les constructions qui servent au logement indispensable à l'entreprise agricole, y compris le logement destiné à la génération qui prend sa retraite, sont réputés conformes à l'affectation de la zone. Cette réglementation reprend les principes dégagés par la jurisprudence de l'ancien art. 16 LAT en vigueur jusqu'au 31 août 2000 (cf. arrêt 1A.205/2004 du 11 février 2005 consid. 3.3 in RDAF 2005 I 365). Un logement n'est réputé conforme à la zone que si la présence permanente sur le domaine des personnes concernée est indispensable, ce qu'il convient d'examiner pour chaque exploitation selon des critères objectifs. Cette question est examinée notamment en fonction de la distance à la zone à bâtir et des tâches de surveillances nécessitées par l'exploitation (cf. <ref-ruling> consid. 3a p. 69, 307 consid. 5 p. 312 ss et les références citées). En revanche, de simples motifs de commodité, de même que des intentions ou des désirs subjectifs, ne sont pas déterminants (cf. <ref-ruling> consid. 3b p. 311; cf. également ALEXANDER RUCH, in Aemisegger/Moor/Ruch/Tschannen, Commentaire LAT, 2010, n. 21 ad art. 16a LAT).
5.2 Les recourants soutiennent que le fait de ne pas pouvoir résider au centre de leur domaine serait un obstacle majeur pour une exploitation conforme aux normes actuelles en matière de protection des animaux et de l'environnement. Ils ne proposent toutefois aucune démonstration de ce qu'ils avancent, n'exposant en particulier pas en quoi la législation actuelle en matière de protection des animaux et de l'environnement - qu'ils n'explicitent au demeurant pas - imposerait un logement en zone agricole. Ils se contentent sur ce point d'affirmer que la présence de l'exploitant sur place est nécessaire en cas de vêlages, de chaleurs, de soins vétérinaires à prodiguer, de problèmes occasionnés par le système de stabulation libre du bétail et d'incidents lorsque les taureaux sont en rut. Les arguments des recourants ne convainquent pas. Ceux-ci ont d'ailleurs démontré qu'il était possible, depuis plusieurs années, d'exploiter leur domaine avec succès quant bien même leur domicile se trouvait à 1,2 kilomètres environ de leur lieu de travail. Ils ne contestent d'ailleurs pas qu'ils peuvent facilement accéder au lieu de détention de leurs animaux par la route. De plus, conformément à la jurisprudence, la proximité immédiate de la zone à bâtir, sise en l'occurrence à environ 50 m, est un élément important pour dénier au projet des recourants la conformité de l'affectation à la zone agricole.
L'habitation projetée paraît davantage reposer sur des considérations personnelles liées notamment à l'état de santé de l'exploitante. Or, si les besoins de réinsertion d'une personne handicapée sont certes compréhensibles, ils ne sont toutefois pas décisifs au regard de la loi et de la jurisprudence précitées (consid. 5.1). Il s'agit d'ailleurs d'un facteur qui a trait uniquement à la personne de l'exploitant et non pas à l'exploitation elle-même. Compte tenu de l'intérêt public à une séparation claire entre les zones constructibles et non constructibles, il convient d'être strict dans l'application des dispositions précitées.
Enfin, les recourants font en vain valoir que pour être viable l'exploitation doit pouvoir disposer de chambre d'hôtes à la ferme, ce qui impliquerait la présence des exploitants sur place. En effet, l'activité d'hébergement que les recourant souhaitent proposer n'a aucun rapport direct avec l'utilisation du sol comme facteur de production, qui définit justement l'activité agricole permettant à ceux qui l'exercent d'habiter, sous certaines conditions, hors des zones à bâtir (cf. <ref-ruling> consid. 4d p. 141 et les références). Par ailleurs, le Tribunal cantonal a retenu que l'exploitation actuelle des recourants répondait aux exigences de professionnalisme et de viabilité selon l'art. 34 al. 4 let. c OAT (cf consid. 2c/bb de l'arrêt entrepris), ce que les recourants n'ont pas formellement contesté.
5.3 Dans ces circonstances, c'est à juste titre que l'instance précédente à considéré que les recourants n'avaient pas établi le caractère indispensable du logement pour leur exploitation. Dès lors, leur projet ne pouvait être autorisé sur la base de l'art. 22 LAT.
6. A défaut d'autorisation au sens de l'art. 22 LAT, le permis de construire ne peut être octroyé, en vertu de l'art. 24 al. 1 LAT, que si l'implantation hors de la zone à bâtir est imposée par la destination de la construction (let. a) et si aucun intérêt prépondérant ne s'y oppose (let. b). Or, au vu des circonstances évoquées ci-dessus (cf. consid. 5.2), la première de ces conditions cumulatives n'apparaît pas remplie, les recourants énonçant d'ailleurs les mêmes arguments que pour le grief précédent. Il n'est dès lors pas nécessaire de contrôler si la seconde condition est réalisée. Au demeurant, l'intérêt public prépondérant lié à une séparation claire entre les zones constructibles et non constructibles justifie le refus d'accorder une autorisation pour la construction d'une habitation sur la parcelle agricole des recourants.
7. Enfin, les recourants invoquent une violation du principe de l'égalité de traitement et de leur droit d'être entendus.
7.1 Une décision viole le principe de l'égalité lorsqu'elle établit des distinctions juridiques qui ne se justifient par aucun motif raisonnable au regard de la situation de fait à réglementer ou lorsqu'elle omet de faire des distinctions qui s'imposent au vu des circonstances, c'est-à-dire lorsque ce qui est semblable n'est pas traité de manière identique et ce qui est dissemblable ne l'est pas de manière différente. Il faut que le traitement différent ou semblable injustifié se rapporte à une situation de fait importante. Les situations comparées ne doivent pas nécessairement être identiques en tous points, mais leur similitude doit être établie en ce qui concerne les éléments de fait pertinents pour la décision à prendre (<ref-ruling> consid. 5.1 p. 125; <ref-ruling> consid. 2b/aa p. 4; <ref-ruling> consid. 6a p. 7 et la jurisprudence citée).
L'inapplication ou la fausse application de la loi dans un cas particulier n'attribue en principe pas à l'administré le droit d'être traité par la suite illégalement. En effet, selon la jurisprudence, le principe de la légalité de l'activité administrative prévaut sur celui de l'égalité de traitement. Exceptionnellement, il est dérogé à cette règle lorsqu'une décision conforme à la loi s'oppose à une pratique illégale que l'autorité a l'intention de continuer de manière générale; le citoyen ne peut donc prétendre à l'égalité dans l'illégalité que s'il y a lieu de prévoir que l'administration persévérera dans l'inobservation de la loi (<ref-ruling> consid. 3a p. 2 s.; <ref-ruling> consid. 6a p. 392; <ref-ruling> consid. 2 p. 82 s. et les arrêts cités). Quoi qu'il en soit, le Tribunal fédéral n'est pas lié par une pratique cantonale contraire au droit fédéral, car il doit veiller à l'application correcte de ce droit (<ref-ruling> consid. 4 p. 234 s.).
7.2 A l'appui de leur grief, les recourants ont réitéré leur demande de production de certains dossiers particuliers relatifs à des cas similaires autorisés en zone agricole par la CCC à Ardon et Vollège; ces dossiers auraient permis de vérifier s'ils pouvaient se prévaloir d'une pratique cantonale autorisant la construction d'habitation en zone agricole. Procédant à une appréciation anticipée des moyens de preuve sollicités, le Tribunal cantonal a considéré que même si les cas évoqués par les recourants présentaient certaines similitudes avec leur cas, le principe de la légalité l'emportait en règle générale sur celui de l'égalité de traitement; il n'était en particulier pas établi que la CCC entendait à l'avenir ne pas appliquer strictement les dispositions de la LAT. Les recourants se contentent en l'espèce d'opposer leur propre appréciation des moyens de preuve requis sans démontrer que les considérations de l'autorité cantonale seraient arbitraires. Leur grief ne répond pas, sur ce point, aux exigences de motivation découlant de l'<ref-law> et est, par conséquent, irrecevable (cf. consid. 3.1 supra). En l'occurrence, une pratique illégale constante de la CCC n'apparaît pas manifeste. Quoi qu'il en soit, une pratique cantonale contraire au droit fédéral en matière d'autorisations fondées sur les art. 22 et 24 LAT ne lierait de toute manière pas le Tribunal fédéral. L'intérêt public à la bonne application de ces dispositions centrales de la LAT doit l'emporter sur une éventuelle prétention à l'égalité dans l'illégalité (cf. <ref-ruling> consid. 4 p. 234 s.; arrêt 1C_89/2009 du 11 juin 2009 consid. 4.2). Le moyen tiré de l'égalité de traitement dans l'illégalité doit par conséquent également être écarté.
8. Il résulte de ce qui précède que le recours doit être rejeté dans la mesure de sa recevabilité. Les recourants, qui succombent, doivent supporter les frais de la procédure (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté, dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 2'000 francs, sont mis à la charge des recourants.
3. Le présent arrêt est communiqué au mandataire des recourants, à la Commune de Fully, au Conseil d'Etat et à la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'à l'Office fédéral du développement territorial.
Lausanne, le 19 mars 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant: Aemisegger
La Greffière: Arn