Faits :
A.
Par ordonnance pénale du 19 janvier 2015, X._ a été condamné pour entrave à l'action pénale, à une peine privative de liberté de six mois, sans sursis, sous déduction de deux jours de détention.
B.
A la suite de l'opposition formée par X._ contre l'ordonnance pénale précitée, le Juge de police de la Veveyse a, par jugement du 29 mai 2015, confirmé sa condamnation pour entrave à l'action pénale ainsi que la peine infligée.
C.
Statuant le 15 décembre 2015 sur l'appel de X._, la Cour d'appel pénal du Tribunal cantonal de l'Etat de Fribourg l'a partiellement admis en ce sens qu'elle l'a condamné à une peine pécuniaire ferme de 90 jours-amende, le montant du jour-amende étant fixé à 40 fr., sous déduction de deux jours-amende correspondant à la détention avant jugement subie.
En bref, il en ressort les faits suivants.
Le 25 juillet 2013, vers 19h35, A._ et son codétenu, B._, se sont évadés de la prison C._, aidés par deux comparses qui ont fait usage d'armes de guerre, afin de tenir en respect les agents pénitentiaires et de sécurité. A._ a été arrêté le 28 août 2013 par la police cantonale vaudoise alors qu'il était passager d'un véhicule conduit par X._. Rapidement, ce dernier a admis avoir hébergé le fugitif et certains de ses comparses à partir des 12, 13, respectivement 18 août 2013. La police a également procédé à des contrôles téléphoniques rétroactifs qui ont permis d'établir l'existence de communications téléphoniques entre X._, un certain D._ et A._ durant la période du 14 juin au 17 juillet 2013.
D.
Le 23 septembre 2013, la réintégration de X._, qui se trouvait en libération conditionnelle d'une peine à vie prononcée en 1984, a été ordonnée. Sa libération a été révoquée (cf. arrêt 6B_720/2014 du 17 novembre 2014).
E.
Le Ministère public de l'Etat de Fribourg forme un recours en matière pénale au Tribunal fédéral contre l'arrêt du 15 décembre 2015, concluant principalement à sa réforme en ce sens que la peine privative de liberté de six mois, sans sursis, sous déduction de deux jours de détention avant jugement, prononcée par jugement du 29 mai 2015 est confirmée. Subsidiairement, il requiert son annulation et le renvoi de la cause à l'autorité précédente pour nouvelle décision.
Invités à se déterminer sur le recours, la cour cantonale y a renoncé, alors que X._ a conclu au rejet. Il sollicite en outre l'assistance judiciaire, comprenant la désignation de son conseil en qualité d'avocat d'office.

Considérant en droit :
1.
Le Tribunal fédéral est lié par les constatations de fait de la décision entreprise (cf. <ref-law>), à moins qu'elles n'aient été établies en violation du droit ou de manière manifestement inexacte au sens des art. 97 al. 1 et 105 al. 2 LTF, soit pour l'essentiel de façon arbitraire au sens de l'art. 9 Cst. (sur la notion d'arbitraire, <ref-ruling> consid. 1.2 p. 308 s., 140 III 16 consid. 2.1 p. 18 s.). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 1.3.1 p. 253 et la référence citée).
2.
Le recourant, se plaignant d'une violation de l'<ref-law>, conteste la peine infligée qu'il juge trop clémente. Il fait valoir que la cour cantonale aurait omis de prendre en compte certains éléments pertinents, respectivement retenu, à tort, des éléments qui n'auraient pas dû l'être.
2.1. Les règles générales régissant la fixation de la peine ont été rappelées dans les arrêts publiés aux <ref-ruling> et 136 IV 55, auxquels on peut se référer.
2.2. La cour cantonale a jugé que l'infraction commise par l'intimé avait consisté à héberger A._ et plusieurs de ses comparses à son domicile et dans un chalet qu'il avait loué pour eux. Il avait en outre effectué des achats pour ces derniers, apporté pour leur compte de l'argent à un individu se trouvant à E._ et véhiculé A._ à deux reprises. Il avait ainsi aidé des fugitifs à se soustraire à la justice, mais seulement de façon temporaire, et sans commettre lui-même d'infractions autres que l'entrave à l'action pénale jugée ici. Il n'avait en particulier pas assisté les fugitifs pour l'évasion proprement dite. A charge, il convenait de retenir que son intervention s'était néanmoins étendue sur une certaine durée puisqu'il avait hébergé les fugitifs pendant plusieurs jours. Les liens personnels et d'amitié le liant à A._, dont il avait fait la connaissance en 2001 alors qu'ils étaient tous deux en détention, devaient également être pris en compte, de même que le fait que, selon les déclarations de l'intimé, A._ lui avait laissé entendre qu'il pourrait tirer un bénéfice financier de l'aide apportée. Ses antécédents, en particulier le fait qu'il s'était vu révoquer sa libération conditionnelle en raison d'un pronostic clairement défavorable ne parlaient pas en sa faveur. Enfin, l'intimé ne pouvait être mis au bénéfice de la circonstance atténuante de l'<ref-law>, dans la mesure où il aurait pu ne pas commettre l'infraction d'entrave à l'action pénale puisque A._ ignorait son adresse et qu'il avait dû diriger les fugitifs au moyen de son téléphone portable; il avait eu, de ce fait, la possibilité de quitter son domicile pour ne pas que les prénommés l'y retrouvent et le menacent. Au vu de ces éléments, la cour cantonale a qualifié la faute de l'intimé de moyennement grave et, tenant compte de son comportement d'une durée limitée, a estimé qu'une sanction de 90 jours-amende ou 90 jours de privation de liberté le punissait équitablement. Elle a ensuite examiné les conditions des art. 41 al. 1, respectivement 42 CP. En l'occurrence, celles de l'<ref-law> n'étaient pas réalisées puisque la seule condamnation dont il s'était rendu coupable dans les cinq ans précédant la commission de l'infraction pour laquelle il était jugé portait sur une infraction à la LCR commise le 28 juillet 2011, sanctionnée par une peine pécuniaire de 45 jours-amende. En outre, dans la mesure où l'intimé s'était vu révoquer sa libération conditionnelle et où il était à nouveau incarcéré, la probabilité qu'il commette à nouveau un délit du même genre était, en l'état, infime. S'il devait à nouveau bénéficier d'une libération conditionnelle, cette appréciation devrait en revanche être revue. En effet, ses antécédents, en particulier le fait que sa libération conditionnelle avait été révoquée à deux reprises en raison du non-respect des conditions qui y avaient été mises, ainsi que l'état de déni dans lequel il se trouvait par rapport aux problèmes qu'il rencontrait, en particulier en ce qui concernait sa problématique alcoolique, faisaient craindre de nouvelles infractions à l'ordre juridique. Dans ces conditions, c'était bien un pronostic défavorable qui devait être posé et le sursis ne pouvait lui être accordé. Il restait à examiner s'il y avait lieu d'admettre que ni une peine pécuniaire ni un travail d'intérêt général ne pourraient être exécutés. Or, si cette réponse devait être résolue par l'affirmative en ce qui concernait le travail d'intérêt général, dont l'exécution s'avérait impossible dès lors que l'intimé était incarcéré, il en allait différemment de la peine pécuniaire. En effet, l'intimé disposait d'une rente AVS de 1'628 fr. et il n'avait pas de frais particuliers puisqu'il était en détention. Dans ces conditions, c'était une peine pécuniaire, de 90 jours-amende, qui devait être prononcée à son encontre.
2.3. Le recourant reproche tout d'abord à l'autorité précédente de ne pas avoir considéré le fait que l'intimé aurait passé sous silence, deux jours après l'évasion, soit avant qu'il n'héberge les évadés, les contacts qu'il avait déjà eus avec A._ et D._, entre le 14 juin 2013 et le 17 juillet 2013, et cela malgré l'information donnée par les autorités vaudoises sur les risques qu'il courait s'il dissimulait des éléments pouvant intéresser l'enquête ou conduire à l'arrestation des fugitifs.
En l'espèce, il ressort du rapport d'investigation établi le 1er juillet 2014 que l'intimé « a été rencontré » par un inspecteur de police deux jours après l'évasion et qu'à cette occasion, il n'a pas parlé des contacts en question, alors qu'il avait été mis en garde des risques encourus s'il dissimulait des éléments qui pourraient intéresser l'enquête, voire conduire à l'arrestation des fugitifs et de leurs complices (cf. <ref-law>; dossier cantonal p. 2105). Aucun procès-verbal d'audition ne figure au dossier et le rapport ne précise pas en quelle qualité il a été interrogé ni si ses droits lui ont été communiqués. Le contenu de cet interrogatoire informel ne saurait dès lors être utilisé contre l'intimé (cf., dans ce sens, MOREILLON/PAREIN-REYMOND, Petit commentaire, Code de procédure pénale, 2e éd. 2016, no 11 ad <ref-law>), ce d'autant que la procédure pénale a également été dirigée contre lui, et qu'en tant que prévenu, il avait le droit de se taire (cf. <ref-law>). Mal fondé, le grief soulevé doit être rejeté.
2.4. Le recourant relève que B._ et A._ ne seraient pas de simples délinquants primaires mais des criminels endurcis, condamnés à des peines élevées, présentant un risque important pour la sécurité publique. Il fait également état de la dangerosité des deux autres comparses qui les ont aidés à s'évader.
Ce faisant, le recourant s'écarte, en partie, des faits retenus par la cour cantonale. Son argumentation est, dans cette mesure, irrecevable. Quoi qu'il en soit, la cour cantonale n'a pas ignoré la dangerosité de ces individus puisqu'elle a considéré que A._ était, à l'instar de l'intimé, incarcéré pour une longue durée, notamment pour séquestration, enlèvement, brigandage qualifié, blanchiment d'argent, vol et incendie intentionnel (cf. arrêt attaqué lettre A p. 2) et que lors de son évasion le 25 juillet 2013 avec son codétenu B._, ils avaient été aidés par deux complices ayant fait l'usage d'armes de guerre, afin de tenir en respect les agents pénitentiaires et de sécurité (cf. supra lettre C). Ces seules considérations révèlent déjà la dangerosité de ces individus, de sorte que l'on ne saurait faire grief à la cour cantonale d'avoir ignoré cet élément. La critique s'avère ainsi infondée dans la mesure de sa recevabilité.
2.5. Le recourant affirme ensuite que la cour cantonale n'aurait pas tenu compte de l'attitude adoptée par l'intimé, qui n'aurait guère été exemplaire, puisque ce ne serait qu'après avoir été confronté à certains éléments de preuve recueillis par les enquêteurs qu'il aurait daigné s'exprimer - seulement partiellement - sur les faits reprochés. Ces éléments ne ressortent toutefois pas de l'arrêt cantonal qui retient que l'intimé a admis rapidement avoir hébergé le fugitif et certains de ses comparses (cf. supra lettre C). Le recourant ne prétend pas ni ne démontre que l'appréciation des juges cantonaux sur ce point serait arbitraire. De nature appellatoire, le grief est irrecevable.
2.6. Pour le reste, lorsque le recourant soutient que l'intimé, ne se contentant pas d'aider son ami A._, aurait prêté main forte à trois autres dangereux délinquants avec lesquels il n'avait aucune relation particulière, qu'il n'aurait pas hésité à les loger, à leur procurer un téléphone portable et à véhiculer l'un d'entre eux à plusieurs reprises, qu'il se serait rendu à E._ pour leur apporter de l'argent ou encore que l'appât du gain, en plus des liens d'amitié, aurait joué un rôle non négligeable dans la décision prise par l'intéressé de fournir son aide aux fugitifs, il ne cite aucun élément qui aurait été ignoré par la cour cantonale (cf. supra consid. 2.2). S'agissant plus particulièrement de la condamnation à la réclusion à vie prononcée à l'encontre de l'intimé, notamment pour l'assassinat de son épouse, la cour cantonale en fait mention dans la partie « considérant en fait » (cf. arrêt entrepris lettre A p. 2) et relève, dans le cadre de la fixation de la peine, que les antécédents de l'intimé ne parlent pas en sa faveur (cf. arrêt entrepris chiffre 3/b p. 5). L'autorité précédente n'a dès lors pas non plus omis cet élément, contrairement à ce qu'affirme le recourant. Pour le surplus, on ne discerne pas en quoi - et le recourant ne l'expose pas - ces éléments auraient dû être appréciés plus largement. Le grief du recourant se révèle dès lors mal fondé.
2.7. Le recourant soutient enfin qu'aucun élément à décharge ne saurait être déduit de la durée des agissements de l'intimé et que ce ne serait que son interpellation inopinée par la police qui y aurait mis fin. Il relève en outre que le fait que l'intimé n'ait joué aucun rôle dans l'évasion elle-même ne serait nullement pertinent, dans la mesure où il n'aurait jamais été question de l'éventuelle application de l'infraction réprimée par l'<ref-law>.
2.7.1. On comprend de la motivation de la cour cantonale qu'elle a tenu compte, à la décharge de l'intimé, du fait qu'il avait aidé les fugitifs à se soustraire à la justice, mais seulement de façon temporaire, en ce sens qu'il les avait hébergés et les avait aidés à subsister, sans toutefois participer à leur évasion. Elle a ensuite considéré qu'il convenait néanmoins de prendre en compte, à la charge de l'intéressé, le fait qu'il avait hébergé les fugitifs sur une certaine durée.
Il était, certes, justifié de prendre en considération la durée de l'intervention de l'intimé puisqu'elle s'est poursuivie pendant plusieurs jours. Il n'était, en revanche, pas admissible de tenir compte, en sa faveur, du fait qu'il n'a joué aucun rôle dans l'évasion. En effet, il n'est pas acceptable de relativiser la gravité de l'entrave à l'action pénale commise par l'intimé, réprimée par l'<ref-law>, au motif qu'il n'a pas participé à l'évasion des fugitifs, ce qui serait constitutif d'une autre infraction (<ref-law>). La gravité de l'acte commis, respectivement l'importance de la faute de l'intimé, ne s'en trouve en rien diminuée. Cet élément, qui constituait tout au plus un facteur neutre dans le cadre de la fixation de la peine, ne pouvait, dès lors, être retenu dans un sens atténuant.
2.7.2. L'entrave à l'action pénale est passible d'une peine privative de liberté de trois ans au plus ou d'une peine pécuniaire (cf. <ref-law>).
En l'espèce, le recourant n'a pas hésité à aider des fugitifs dangereux à se soustraire à la justice, en les hébergeant et en les aidant à subsister durant plus de deux semaines, alors même qu'il se trouvait en libération conditionnelle. Il a commis ces faits par appât du gain, alors qu'il aurait été facile pour lui de les éviter puisqu'aucune menace n'était exercée sur lui lorsqu'il a communiqué son adresse aux fugitifs et le chemin pour s'y rendre. Il a en outre des antécédents. Les seuls liens personnels et d'amitié que l'intimé entretenait avec A._ retenus en sa faveur par la cour cantonale, ne font pas contre-poids aux autres éléments qui lui sont défavorables. Dans ces circonstances et à s'en tenir à ces constatations de fait, dont le caractère arbitraire n'a pas été allégué ni démontré par l'intimé (cf. <ref-law>), force est d'admettre que la peine pécuniaire de 90 jours-amende qui a été infligée à ce dernier - qui entre dans les premiers degrés de l'échelle des sanctions envisageables pour une infraction à l'<ref-law> - apparaît insuffisante et doit être qualifiée d'abusivement clémente.
2.8. Il s'ensuit que le recours doit être admis et l'arrêt attaqué annulé, la cause étant renvoyée à l'autorité cantonale pour qu'elle fixe à nouveau la peine.
3.
Le ministère public, qui obtient gain de cause, ne saurait se voir allouer de dépens (<ref-law>). La requête d'assistance judiciaire de l'intimé doit être admise au vu de sa situation financière et une indemnité appropriée doit être accordée à son conseil d'office, à charge de la caisse du Tribunal fédéral (<ref-law>). L'intimé est toutefois rendu attentif au fait qu'il devra rembourser cette dernière, s'il peut ultérieurement le faire (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour nouvelle décision.
2.
La demande d'assistance judiciaire de X._ est admise pour la procédure devant le Tribunal fédéral.
3.
Il n'est pas perçu de frais judiciaires.
4.
Me Jean Lob est désigné comme avocat d'office de X._ et une indemnité de 1'000 fr., supportée par la caisse du Tribunal fédéral, lui est allouée à titre d'honoraires.
5.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal de l'Etat de Fribourg, Cour d'appel pénal.
Lausanne, le 21 novembre 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Nasel