Faits :
A.
Le 18 octobre 1986, A.A._ et B.A._ ont acquis aux enchères publiques, pour un prix de 37'000 fr., la parcelle n o 5076, folio 44, située au lieu-dit "Ferrage" sur le territoire de la Commune de Martigny. Selon l'extrait cadastral reproduit dans le procès-verbal de vente, ce bien-fonds présente une superficie de 1'389 m 2 répartie en 1'368 m 2 de champ et 21 m 2 supportant une habitation-remise. A l'époque de la vente, cette parcelle était classée en zone XII sans affectation spéciale au sens de l'art. 90 de l'ancien règlement communal des constructions approuvé le 4 juillet 1984 par le Conseil d'Etat du canton du Valais. Le règlement communal des constructions et des zones (RCCZ), homologué en 1986, colloque ce bien-fonds en zone agricole.
A.A._ et B.A._ sont également copropriétaires, depuis 2000, de la parcelle agricole contigüe n o 5077.
B.
Le 7 février 1991, A.A._ a déposé auprès de l'administration communale de Martigny une demande d'autorisation portant sur la construction d'un "pavillon de campagne" en remplacement du pavillon en bois initialement présent sur le bien-fonds "complètement détruit par les flammes", selon ses dires. Le projet portait sur la reconstruction en dur et d'une forme différente respectant la surface initiale, d'environ 38 m 2.
Le 28 février 1991, le prénommé a informé la Municipalité de Martigny que, "suite aux décisions connues verbalement", il renonçait à son projet et limitait sa demande d'autorisation à la rénovation et à la reconstruction du pavillon détruit par les flammes.
Le 29 avril 1991, la commune a signalé à l'intéressé que son projet contrevenait au RCCZ; si une cabane était reconstruite, selon les nouveaux plans, la surface de celle-ci ne devrait en principe pas dépasser 20 m 2. En vertu des droits acquis, la commune a néanmoins autorisé la reconstruction de la baraque existante dans le même gabarit que celle partiellement détruite (925 cm x 425 cm, toit à pan d'une hauteur au faîte de 360 cm sur panne et de 250 cm sur panne à la sablière), interdisant toutefois la réalisation d'aménagements intérieurs autre que ceux destinés au rangement d'outils ou de machines.
Lors de la reconstruction en 1991, des pavés ainsi que des dalles préfabriquées ont été posés autour de la maisonnette.
C.
Par décision du 21 avril 1998, la commune de Martigny a délivré à A.A._ - après publication officielle - l'autorisation d'édifier entre la parcelle n o 5076 et le bien-fonds n o 5075, propriété de son frère, C.A._, un mur d'une longueur de 32 m.
Le 1 er avril 1999, C.A._ a signalé à la Commission cantonale des constructions (ci-après: CCC) que ce mur avait été autorisé par une autorité incompétente; il a en outre dénoncé la présence d'un couvert en toile/bâche disposé par A.A._ entre le bâtiment reconstruit en 1991 et le mur en question.
Interpelé par la Police cantonale des constructions (ci-après: PoCo), A.A._ a indiqué, le 27 avril 1999, que la reconstruction de la cabane de jardin de même que l'édification du mur de clôture se fondaient sur des autorisations communales délivrées respectivement les 29 avril 1991 et 21 avril 1998.
Par décision du 5 mai 1999, la CCC a formellement autorisé le mur de clôture.
Sur nouvelle interpellation de C.A._, la CCC a, par décisions des 15 et 23 mars 2000, intimé à A.A._ l'ordre de cesser tous travaux sur la parcelle n o 5076 et de supprimer le couvert créé par la bâche susmentionnée.
Le 27 mars 2000, après s'être rendu sur les lieux, le responsable de la PoCo a informé C.A._ qu'il ne voyait, en l'état, aucun motif d'intervenir.
D.
Par décision du 7 septembre 2000, le Conseil municipal de Martigny a délivré à A.A._ une autorisation portant sur l'édification d'une cabane de jardin sur la parcelle n o 5077; il était précisé que cette construction ne devait comporter aucun équipement technique propre à l'habitat et être dépourvu d'isolation thermique.
Le 15 juillet 2005, C.A._ a informé la CCC que la cabane nouvellement édifiée sur le fonds n o 5077 avait été aménagée pour l'habitation; il a en outre indiqué que A.A._ ne s'était pas conformé aux décisions rendues les 15 et 23 mars 2000.
Par décision du 20 octobre 2005, sur la base d'un rapport d'inspection de la PoCo du 22 août 2005, la CCC a exhorté A.A._ de supprimer le couvert-abri, la dalle et la pergola/treille se trouvant devant la cabane de jardin de la parcelle n o 5077 et de restituer au terrain sa vocation agricole par le biais d'une revégétalisation.
A.A._ et B.A._ ont en vain déféré ce prononcé au Conseil d'Etat avant de déposer un recours auprès de la Cour de droit public du Tribunal cantonal du Valais, recours qu'ils ont retiré le 10 août 2007.
Suite au retrait du recours, la PoCo a procédé à une nouvelle inspection locale le 22 novembre 2007. A cette occasion, il a été constaté que le couvert en panneaux de coffrage et la bâche avaient été démontés, mais qu'il n'en allait pas de même de la dalle et de la treille aménagées sur la parcelle n o 5077. Le 31 janvier 2008, la CCC a enjoint à A.A._ d'achever la remise en état ordonnée le 20 octobre 2005.
Dans l'intervalle, C.A._ a, le 29 octobre 2007, adressé une nouvelle dénonciation à la CCC, se plaignant de la construction sur les fonds voisins d'un mur de soutènement réalisé dans la meunière, de la reconstruction d'un grill et de l'aménagement d'une place de parc.
E.
Le 13 mai 2008, la PoCo a informé A.A._ et B.A._ que, suite aux différentes procédures de police des constructions, il était prévu de faire un bilan de l'ensemble des constructions édifiées sur les parcelles n os 5076 et 5077. Une nouvelle inspection locale a été mise sur pied à cette fin, le 28 mai 2008, en présence des intéressés.
Approchée par C.A._, la PoCo a informé ce dernier, par courrier du 20 avril 2010, qu'il apparaissait, sur la base des constatations réalisées le 28 mai 2008, que les différents ordres de remises en état avaient été effectués. Elle lui a également précisé que le mur de soutènement avait été réalisé avec l'accord des services techniques de la commune. La commune avait par ailleurs confirmé que le grill remis en état existait avant 1991. Ce courrier précisait encore que la situation avait été présentée à la CCC, laquelle avait pris note des remises en état opérées et indiqué qu'aucune nouvelle décision n'avait été prise. La commission cantonale regrettait cependant le manque de connaissance des communes valaisannes en matière de répartition des compétences avec le canton dans le domaine de la police des constructions; elle précisait à ce propos que des séances seraient organisées pour les instruire de ces questions.
C.A._ a remis en cause certaines constatations réalisées par la PoCo le 28 mai 2008; une nouvelle inspection locale, diligentée par la vice-présidente de la CCC, a par conséquent été organisée, le 23 juin 2010.
Par décision du 5 mai 2013, communiquée le 31 mai 2013, la commission cantonale a constaté que sur les 2021 m 2 que totalisent les parcelles agricoles n os 5076 et 5077, plus d'un tiers était dévolu aux loisirs, à la détente ainsi qu'à l'habitation; la CCC a ainsi ordonné une remise en état conforme au droit. Elle a en particulier exigé de rendre à la maisonnette sise sur le fond n o 5076 sa vocation agricole en supprimant tous les aménagements propres à l'habitat (cuisine, chauffage, cheminée, ameublement, etc.) ainsi que les volets. Le couvert attenant à cette cabane devait également être enlevé, de même que les aménagements qu'il abrite (grill, four, antenne parabolique). La commission cantonale a également ordonné à A.A._ de retirer le dallage en béton entre cette maisonnette et le mur séparant la parcelle du fonds n o 5075; elle a aussi requis la suppression de l'ensemble des autres aménagements extérieurs (pavés, dalettes, grill, fontaine, jeux, haie de thuyas) et le démantèlement des clôtures, murets, pilastres, portails et treillis. La CCC a par ailleurs imposé une revégétalisation naturelle ou une mise en culture adéquate des différentes surfaces concernées. La commission cantonale a enfin exigé le dépôt d'une demande de permis de construire s'agissant du mur de soutènement réalisé dans la meunière.
En application du principe de la proportionnalité, la CCC a en revanche renoncé à ordonner la suppression de la surélévation du terrain constatée sur le fonds n o 5076, figurant sur des plans acceptés par la commune en 1999. Il en va de même des autres éléments formellement autorisés, à savoir le mur de séparation, la cabane de jardin sur le bien-fonds n o 5077, ainsi que le goudronnage de la zone de croisement.
A.A._ et B.A._ ont saisi le Tribunal cantonal après avoir contesté sans succès cet ordre de démolition devant le Conseil d'Etat. Par arrêt du 7 avril 2017, la cour cantonale a rejeté leur recours. Cette dernière a en substance considéré que les recourants ne pouvaient se prévaloir ni de leur bonne foi ni de la garantie de la situation acquise pour faire obstacle à la remise en état des lieux litigieuse.
F.
Agissant par la voie du recours en matière de droit public, A.A._ et B.A._ demandent au Tribunal fédéral d'annuler l'arrêt attaqué ainsi que la décision de remise en état prononcée par la CCC. Ils requièrent par ailleurs l'octroi de l'effet suspensif.
Le Tribunal cantonal renonce à se déterminer. Le Conseil d'Etat se rallie aux considérants de l'arrêt entrepris. Egalement invité à se prononcer, l'Office fédéral du développement territorial ARE renonce à formuler des observations, l'arrêt attaqué ne lui paraissant pas critiquable.
Par ordonnance du 7 juin 2017, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif.
Considérant en droit :
1.
Dirigé contre une décision finale (art. 90 LTF) prise en dernière instance cantonale (art. 86 al. 1 let. d LTF) dans le domaine du droit public des constructions (art. 82 let. a LTF), le recours est en principe recevable comme recours en matière de droit public selon les art. 82 ss LTF, aucune des exceptions prévues à l'art. 83 LTF n'étant réalisée. Les recourants ont pris part à la procédure de recours devant le Tribunal cantonal. En tant que destinataires de l'ordre de remise en état relatif aux parcelles dont ils sont propriétaires, les recourants peuvent se prévaloir d'un intérêt personnel et digne de protection à l'annulation de l'arrêt attaqué. Ils ont dès lors qualité pour recourir au sens de l'art. 89 al. 1 LTF. Les autres conditions de recevabilité sont au surplus réunies, si bien qu'il y a lieu d'entrer en matière.
2.
A titre de mesure d'instruction, les recourants sollicitent la production des dossiers constitués par le Tribunal cantonal et la Commission cantonale des constructions. Cette demande est satisfaite, l'instance précédente ayant déposé son dossier - comprenant également ceux des autres autorités concernées - dans le délai imparti à cette fin (art. 102 al. 2 LTF).
3.
Les recourants se plaignent d'une constatation inexacte des faits.
3.1. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). La partie recourante ne peut critiquer ceux-ci que s'ils ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (ATF 140 III 264 consid. 2.3 p. 266) - ou en violation du droit au sens de l'art. 95 LTF (art. 97 al. 1 LTF), ce qu'il lui appartient d'exposer et de démontrer de manière claire et circonstanciée (art. 106 al. 2 LTF). La correction du vice soulevé doit en outre être susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF).
3.2. Selon les recourants, la cour cantonale aurait à tort dénié à la lettre de la CCC du 20 avril 2010 (cf. partie Faits, let. E) le caractère d'une décision de classement définitif de leur dossier. Ils omettent cependant de préciser qu'ils n'étaient pas destinataires de ce courrier, lequel était adressé à leur voisin, le frère du recourant. Pour ce motif déjà, il apparaît douteux que ce document puisse être assimilé à une décision. Quoiqu'il en soit, au regard de son contenu, il n'est pas arbitraire de lui avoir refusé cette qualification, la CCC se limitant à y indiquer avoir pris note, lors de sa séance du 7 octobre 2008, que les remises en état alors exigées avaient été exécutées et que les constructions récentes avaient été autorisées par la commune; ce courrier ne fait en revanche pas mention d'un quelconque classement définitif.
C'est ensuite à tort que les recourants prétendent que la cour cantonale n'aurait pas indiqué l'ensemble des visites des lieux effectuées par la CCC: les inspections de 2005, 2007 et 2008, prétendument omises par l'instance précédente, sont en effet expressément mentionnées dans l'état de fait cantonal et prises en compte dans les considérants de l'arrêt attaqué; elles se révèlent par ailleurs sans influence sur l'issue du litige, la connaissance de longue date de la situation par la CCC n'étant pas de nature à remettre en question l'ordre de démolition (cf. consid. 4.1.2).
Il est enfin également erroné d'affirmer que la cour cantonale aurait négligé de tenir compte de la vocation d'habitation de la maisonnette initialement supportée par la parcelle n o 5076 et de l'indication de celle-ci au registre foncier ("habit. remise"). Ce point ressort en effet de l'état de fait cantonal. En outre, aux termes des considérants de son arrêt, l'instance précédente a expressément retenu que cette maisonnette préexistante était équipée d'une cuisinière, d'un chauffage et de meubles d'habitat. Elle a toutefois jugé ces éléments sans pertinence, les recourants n'ayant ni prétendu ni a fortiori démontré que la construction originelle était antérieure à l'introduction, le 1 er juillet 1972, de la séparation entre les parties constructibles et non constructibles du territoire (cf. à ce sujet, RUDOLF MUGGLI, Commentaire pratique LAT: construire hors zone à bâtir, 2017, n. 17 ss ad art. 24c LAT; voir également consid. 5.1 ci-dessous) et que cet ouvrage devait, pour ce motif, bénéficier de la garantie de la situation acquise de l'art. 24c de la loi fédérale sur l'aménagement du territoire du 22 juin 1979 (LAT; RS 700). Devant le Tribunal fédéral, les recourants ne le soutiennent d'ailleurs pas non plus, réservant cette argumentation pour le couvert présent sur la parcelle n o 5076 et ses aménagements (cf. consid. 5). La présente critique se révèle partant infondée.
3.3. Mal fondées, les critiques relatives à l'établissement des faits doivent être rejetées.
4.
Les recourants se plaignent, à différents égards, d'une violation du principe de la bonne foi.
4.1. Ils soutiennent en premier lieu que la maisonnette érigée sur le fonds n o 5076, le dallage de béton entre celle-ci et le mur de séparation d'avec la parcelle n o 5075, les pavés et dalles préfabriqués l'entourant, de même que la haie de thuyas, devraient être mis au bénéfice d'un droit acquis né de "la confiance [qu'ils] pouvaient avoir de bonne foi face à l'inaction répétée de l'autorité cantonale".
4.1.1. Selon la jurisprudence, la compétence d'exiger la démolition d'une installation sise hors de la zone à bâtir pour rétablir une situation conforme au droit est soumise, de par le droit fédéral, à un délai de péremption de trente ans, que les cantons ne sont pas habilités à assouplir (cf. arrêt 1C_150/2016 du 20 septembre 2016 consid. 10.4 et 10.5 et les arrêts et références cités). Exceptionnellement, cette compétence peut être exercée au-delà du délai en question si des motifs de police au sens strict imposent une telle mesure. Inversement, l'autorité peut en être déchue avant l'écoulement des trente ans lorsque le principe de la confiance le commande (cf. ATF 136 II 359 consid. 7 p. 365 ss; 132 II 21 consid. 6.3 p. 39; arrêt 1C_412/2016 du 1 er décembre 2016 consid. 2.5). C'est notamment le cas lorsque l'autorité compétente a toléré pendant des années un état dont elle connaissait ou aurait dû connaître l'illégalité; cependant seul celui qui a agi de bonne foi peut y prétendre (cf. ATF 136 II 359 consid. 7 p. 365 ss; 132 II 21 consid. 6.3 p. 39).
4.1.2. Il faut concéder aux recourants que le traitement du dossier par la CCC n'est pas exempt de tout reproche - ce que n'a d'ailleurs pas manqué de souligner l'instance précédente. Il ressort à cet égard des constatations cantonales que l'autorité a en effet attendu 2013 pour intervenir, en dépit des inspections locales répétées de la PoCo, diligentées postérieurement à la réalisation des ouvrages litigieux. La CCC ne pouvait ainsi plus ignorer, dès l'année 2000 (cf. partie Faits, let. C), date de la première inspection, le caractère illicite de la situation, comme l'a d'ailleurs retenu le Tribunal cantonal.
L'inaction de la commission cantonale est cependant insuffisante à faire échec à l'ordre de remise en état contesté. En effet, la déchéance du droit de requérir, pour ce motif, le rétablissement d'une situation conforme au droit présuppose, selon la jurisprudence, que le propriétaire puisse se prévaloir de sa bonne foi (cf. ATF 136 II 359 consid. 7 p. 365 ss; 132 II 21 consid. 6.3 p. 39). Cette condition n'est en l'occurrence cependant pas réalisée. En effet, indépendamment de sa validité, l'autorisation de reconstruire une cabane sur la parcelle n o 5076, délivrée en 1991 par la commune, exigeait qu'aucun aménagement intérieur autre que celui destiné au rangement d'outils et de machine ne soit réalisé; elle imposait de même le maintien du gabarit initial. Or il ressort du dossier, en particulier des constats de la PoCo et des nombreuses photographies versées en cause, que les recourants sont manifestement passés outre les termes de ce permis de construire: la maisonnette est ainsi non seulement - et notamment - équipée d'une cuisine, mais également d'un chauffage ainsi que d'une cheminée; elle est en outre munie de volets; elle ne respecte par ailleurs pas non plus le gabarit autorisé, dépassement toutefois toléré par la CCC en application du principe de proportionnalité. La reconstruction des éléments extérieurs ne faisait pas non plus l'objet de l'autorisation de construire délivrée en 1991. Dans ces circonstances, les recourants ne sauraient sérieusement prétendre avoir, de bonne foi, cru pratiquer une utilisation de leur parcelle conforme à cette autorisation de construire, pour faire échec à la décision de remise en état, intervenue avant l'échéance du délai de péremption de trente ans.
4.2. Toujours sous l'angle de la violation du principe de la bonne foi, les recourants allèguent s'être fiés aux autorisations orales portant sur certains des ouvrages en procès communiquées par la commune, dont ils ne pouvaient déceler l'incompétence.
4.2.1. Découlant directement de l'art. 9 Cst. et valant pour l'ensemble de l'activité étatique, le droit à la protection de la bonne foi préserve la confiance légitime que le citoyen met dans les assurances reçues des autorités, lorsqu'il a réglé sa conduite d'après des décisions, des déclarations ou un comportement déterminé de l'administration. Selon la jurisprudence, un renseignement ou une décision erronés de l'administration peuvent obliger celle-ci à consentir à un administré un avantage contraire à la réglementation en vigueur, à condition que l'autorité soit intervenue dans une situation concrète à l'égard de personnes déterminées, qu'elle ait agi ou soit censée avoir agi dans les limites de ses compétences et que l'administré n'ait pas pu se rendre compte immédiatement de l'inexactitude du renseignement obtenu. Il faut encore que l'administré se soit fondé sur les assurances ou le comportement dont il se prévaut pour prendre des dispositions auxquelles il ne saurait renoncer sans subir de préjudice, et que la réglementation n'ait pas changé depuis le moment où l'assurance a été donnée (ATF 131 II 627 consid. 6.1 p. 637; 129 I 161 consid. 4.1 p. 170; 122 II 113 consid. 3b/cc p. 123; 99 Ib 94 consid. 4 p. 101 s. et les références citées; ATF 2C_120/2010 du 16 décembre 2010).
4.2.2. Il n'est à ce stade ni contesté ni contestable que l'autorité communale ne bénéficiait pas de la compétence de délivrer des permis de construire hors de la zone à bâtir (cf. art. 25 al. 2 aLAT [RO 1979 1573]; art. 25 al. 2 LAT, dans sa version en vigueur depuis le 1er septembre 2000; art. 2 al. 1 let. b de la loi sur les constructions du 8 février 1996 [LC; RS/VS 705.1]); les différentes autorisations délivrées aux recourants sont ainsi frappées de nullité, les ouvrages en cause ne pouvant être régularisés a posteriori (cf. arrêt 1C_486/2015 du 24 mai 2016 consid. 3.1), faute d'être conformes à la zone agricole, ce que les recourants ne contestent d'ailleurs pas céans. Ces derniers soutiennent en revanche qu'à l'époque des réalisations litigieuses, il ne leur était pas possible d'identifier cette incompétence et affirment s'être ainsi fiés de bonne foi aux autorisations orales communiquées par l'administration communale. Selon eux, ces assurances feraient obstacle à une remise en état des clôtures, grillages, portail et murs de soutènement érigés sur leurs parcelles.
Cette argumentation ne peut être suivie. Tout d'abord, comme l'a relevé le Tribunal cantonal, les différentes autorisations dont il est ici question n'émanaient pas formellement de la municipalité, mais du service technique, lequel ne bénéficie à l'évidence pas d'un pouvoir décisionnel en la matière. Les aménagements en cause n'ont ensuite fait l'objet d'aucune mise à l'enquête, dont la nécessité n'était pourtant pas inconnue des recourants: cette procédure leur avait déjà été imposée en 1991, lors de la reconstruction de la maisonnette détruite par les flammes, ainsi que pour l'édification d'un mur de séparation en 1998. L'informalité des autorisations délivrées oralement était ainsi aisément reconnaissable. La compétence de la CCC en matière d'autorisations hors de la zone à bâtir figure par ailleurs en toutes lettres, avec l'indication de la disposition légale topique (cf. art. 2 LC), dans l'ordre d'arrêt des travaux du 15 mars 2000 ainsi que - en caractère gras, qui plus est - dans la décision de remise en état des lieux du 23 mars 2000; les recourants ne pouvaient ainsi ignorer cet aspect de la procédure. Il est dès lors sans conséquence que la commission cantonale se soit plainte, dans son courrier du 20 avril 2010 au voisin des recourants, de la méconnaissance des communes valaisannes s'agissant de la répartition des compétences en matière d'autorisation de construire. C'est enfin également en vain que les recourants se prévalent de leur nationalité étrangère et affirment ne bénéficier que d'une "formation primaire", ce qui ne leur permettrait pas de percevoir toutes "les subtilités du système administratif suisse". Outre que cet aspect de la situation ne ressort pas de l'arrêt entrepris (art. 105 al. 1 LTF) - et semble d'ailleurs démenti par les correspondances en langue française rédigées par le recourant dans le cadre, notamment, de la demande de reconstruction de la cabane de 1991 (à titre d'exemple, cf. dossier CCC, pièce A, lettres des 7 et 28 février 1991) -, cela ne dispensait pas les recourants de se renseigner sur les restrictions imposées par l'affectation agricole de leurs bien-fonds, d'autant moins que cette problématique est l'objet de discordes récurrentes avec leur voisin, à tout le moins depuis 1999 (cf. dossier CCC, pièce 1, courrier de la CCC au recourant du 9 avril 1999). On peut d'ailleurs douter que les informations pertinentes ne leur aient pas été communiquées par l'avocat qu'ils ont consulté dans le cadre de la procédure d'arrêt des travaux de 1999 (cf. dossier CCC, pièce 1, courrier de Me D._ du 27 avril 1999).
Dans ces conditions, les installations litigieuses ne sauraient être tolérées au bénéfice des assurances communiquées oralement par les autorités communales.
4.3. Entièrement mal fondés, les griefs tirés d'une violation du principe de la bonne foi doivent être rejetés.
5.
Les recourants invoquent une violation de l'art. 24c LAT. Ils avancent que le couvert litigieux et ses aménagements (sol en béton et grill) ont été reconstruits en application de l'art. 9 ch. 3 du décret valaisan sur la procédure d'autorisation de construire du 31 janvier 1992 et qu'ils devraient, pour ce motif, bénéficier du droit acquis de l'art. 24c al. 1 LAT, admettant ainsi, à tout le moins implicitement, la non-conformité à la zone agricole de ces installations.
Le décret cantonal - dont les termes reproduits dans l'arrêt attaqué ne sont pas contestés - exemptait d'autorisation, dans le cadre de l'usage local ou conformément à d'autres prescriptions communales et sous réserve de dispositions communales plus restrictives, les petites constructions et installations privées annexes telles que les places de jardin non couvertes et ouvertes sur les deux côtés au moins, les cheminée de jardin, les bacs à sable et les bassins pour les enfants (art. 9 ch. 3 let. a); il en était de même pour les installations et aménagements extérieurs de jardin privé tels que sentiers, escaliers, fontaines, sculptures, ainsi que les murs de clôtures, de soutènement de revêtement ne dépassant pas 1,50 m de hauteur ou une hauteur légalement prescrite (art. 9 ch. 3 let. b).
5.1. Selon l'art. 24c al. 1 LAT, hors de la zone à bâtir, les constructions et installations qui peuvent être utilisées conformément à leur destination mais qui ne sont plus conformes à l'affectation de la zone bénéficient en principe de la garantie de la situation acquise. L'art. 24c LAT n'est cependant pas applicable aux constructions dont la non-conformité est due à un comportement illicite, même si le rétablissement de l'état conforme au droit n'a pas pu être effectué pour des raisons de proportionnalité, de prescription ou de péremption (cf. arrêt 1C_486/2015 du 24 mai 2016 consid. 2.1.1 et les arrêts et références cités; RUDOLF MUGGLI, Commentaire pratique LAT: construire hors zone à bâtir, 2017, n. 15 ad art. 24c LAT); la non-conformité doit résulter d'une modification de la situation juridique (cf. RUDOLF MUGGLI, Commentaire LAT, 2010, n. 11 ad art. 24c LAT).
Or, en l'occurrence, les recourants ne prétendent pas que la non-conformité des installations litigieuses serait la conséquence d'une telle modification: ils n'avancent en particulier pas que ces aménagements seraient devenus illicites le 1er juillet 1972, lors de l'introduction, sur le plan fédéral, du principe de la séparation entre territoire bâti et non bâti (à ce sujet, cf. RUDOLF MUGGLI, Commentaire pratique LAT: construire hors zone à bâtir, 2017, n. 17 ss ad art. 24c LAT) - ce qui ne ressort au demeurant pas du dossier; ils ne soutiennent pas non plus qu'il en aurait été ainsi à l'occasion du passage d'une zone "sans affectation spéciale" - dont ils ne contestent du reste pas le caractère inconstructible - en zone agricole, avec l'adoption du RCCZ, homologué le 14 avril 1996 (cf. partie Faits, let. A). Il s'ensuit que les recourants ne pouvaient être mis au bénéfice de la protection de la situation acquise, lors de la reconstruction de ces aménagements. On ne discerne par ailleurs pas en quoi ces reconstructions, prétendument fondées sur l'art. 9 ch. 3 du décret cantonal, accorderaient aujourd'hui un tel droit acquis: cette disposition ne porte en effet pas sur la conformité à l'affectation de la zone. Les recourants faillissent du reste à démontrer qu'il existait, à l'époque des constructions, un usage local leur permettant de réaliser celles-ci librement et sans autorisation, dans un secteur situé hors de la zone à bâtir; leur argumentation à cet égard est en effet purement appellatoire, les recourants se bornant à affirmer, sans autre forme d'explication, qu'il serait "de notoriété publique que les communes valaisannes s'arrogeraient le droit d'autoriser de petites constructions, même hors zone à bâtir", ce qui est insuffisant au regard des exigences de motivation des art. 42 al. 2 et 106 al. 2 LTF.
5.2. Entièrement mal fondé, ce grief doit être rejeté.
6.
Les recourants se plaignent enfin d'une application arbitraire de l'art. 51 al. 1 à 3 et 5 et de l'art. 52 LC. Leur argumentation ne porte toutefois que sur l'application de l'art. 51 LC, de sorte qu'il n'est pas nécessaire de s'attarder sur la disposition qui le suit (art. 106 al. 2 LTF).
6.1. Aux termes de l'art. 51 LC, lorsqu'un projet est exécuté sans autorisation de construire ou contrairement à l'autorisation délivrée, ou que lors de l'exécution d'un projet autorisé des dispositions sont violées, l'autorité compétente en matière de police des constructions ordonne l'arrêt total ou partiel des travaux et le fait observer; lorsque les circonstances l'exigent, elle peut ordonner l'interdiction d'utiliser les bâtiments et installations illicites. Ces décisions sont immédiatement exécutoires (al. 1). L'autorité de police des constructions fixe au propriétaire ou au titulaire d'un droit de superficie un délai convenable pour la remise en état des lieux conforme au droit sous la menace d'une exécution d'office (al. 2). Quant à l'alinéa 3, il renferme les éléments que doit contenir la décision de remise en état, à l'instar des voies de droit (let. e) ou encore des menaces d'exécution forcée (let. c). L'art. 51 al. 5 LC prévoit que dix ans après le jour où l'état de fait contraire au droit était reconnaissable, la remise en état des lieux ne peut être exigée que si elle est commandée par des intérêts publics impératifs. La prescription absolue est de 30 ans dès l'achèvement des travaux.
6.2. Les recourants soutiennent en premier lieu que le délai de prescription de dix ans prévu par l'art. 51 al. 5 LC serait échu. Ils affirment ensuite qu'au vu des nombreuses inspections locales réalisées par la CCC, celle-ci serait en tout état déchue de son droit d'exiger une remise en état. Enfin, les recourants répètent que les différentes constructions litigieuses ont été autorisées par la commune et qu'ils étaient partant au bénéfice du principe de la confiance. Dans ces circonstances, selon les recourants, l'ordre de remise en état litigieux relèverait d'une application arbitraire de l'art. 51 al. 1 à 3 et 5 LC.
6.3. Les recourants perdent tout d'abord de vue - cela a été rappelé ci-dessus (cf. consid. 4.1.1) - que le droit fédéral prévoit, hors de la zone à bâtir, un délai de péremption de trente ans pour le rétablissement d'un état conforme, et ne laisse pas de place à une réglementation cantonale moins rigoureuse. Par ailleurs, la problématique de la déchéance du droit d'exiger le retour à un état conforme au droit, telle qu'exposée à l'appui du présent grief, ne relève pas de l'application du droit cantonal, mais de la question de la bonne foi des recourants au moment de la réalisation des constructions concernées, point également traité ci-dessus (cf. consid. 4.1.2). Il en est de même de la problématique de la confiance que les recourants pouvaient accorder aux autorisations délivrées par la commune, qui ne relève pas non plus, à strictement parler, de l'application de l'art. 51 LC (cf. consid. 4.2.2).
6.4. Sans portée propre ce grief doit être écarté.
7.
Devant le Tribunal fédéral, les recourants ne font enfin plus valoir que la remise en état litigieuse violerait le principe de la proportionnalité: ils ne remettent en particulier pas en cause l'intérêt public à la séparation du territoire bâti et non bâti poursuivi par la mesure litigieuse (à ce sujet, cf. ATF 132 II 21 consid. 6.4 p. 40; 111 Ib 213 consid. 6b p. 225) ni ne soutiennent que l'exécution de cette dernière entraînerait des conséquences financières démesurées, aspects qu'il n'appartient pas au Tribunal fédéral d'examiner d'office (art. 106 al. 2 LTF). Dans ces circonstances, il peut, s'agissant de ces questions, être renvoyé aux considérants pertinents de l'arrêt attaqué (cf. art. 109 al. 3 LTF).
En définitive, faute pour les recourants de pouvoir se prévaloir de leur bonne foi, la mesure litigieuse, proportionnée et répondant à un intérêt public cardinal en matière d'aménagement du territoire, doit être confirmée.
8.
Il s'ensuit que le recours doit être rejeté, aux frais des recourants, qui succombent (art. 66 al. 1 LTF). Il n'y a pas lieu d'allouer de dépens (art. 68 al. 3 LTF).
Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge des recourants.
3.
Le présent arrêt est communiqué au mandataire des recourants, à la Commune de Martigny, au Conseil d'Etat du canton du Valais, au Tribunal cantonal du canton du Valais, Cour de droit public, et à l'Office fédéral du développement territorial.
Lausanne, le 14 novembre 2017
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Merkli
Le Greffier : Alvarez