Faits : A. A.a. Par acte d'avancement d'hoirie instrumenté le 27 mai 2011, A.A._ a cédé à sa fille B.A._ la propriété des parcelles nos 5422, 5423 et 5424. Il est en revanche demeuré propriétaire de la parcelle no 5440. Les parcelles précitées sont situées au lieu-dit " X._ ", dans la zone à bâtir de la commune de U._ (ci-après la commune). A.b. Les parcelles nos 5422 à 5424 sont contigües. Elles sont bordées, au nord, respectivement au nord-est, par le chemin F._ (anciennement appelé chemin G._) et, au sud, par la route H._. La parcelle no 5440 est bordée au nord/nord-est par le chemin F._. A.c. Selon le point de vue défendu par A.A._ et B.A._, que conteste la commune, celle-ci a élargi le chemin F._ dès 1975 d'un mètre et plus, pris sur les parcelles situées en amont (sur la droite en descendant), un bisse, désormais partiellement couvert se trouvant de l'autre côté; la commune a également construit le mur qui soutient le talus amont. Toujours selon les susnommés, tous les propriétaires riverains de l'époque auraient laissé la commune utiliser les terrains pour procéder à l'élargissement du chemin F._ tout en demeurant propriétaires de la surface correspondante. A.A._ et B.A._ en veulent pour preuve que C._, propriétaire notamment de la parcelle no 5434 - située entre les biens-fonds des intéressés -, a signé en 1975 une convention avec la commune qui prévoyait, entre autres, la constitution d'une servitude de passage en faveur de la collectivité publique correspondant à l'emprise de la route. Aucune procédure d'expropriation formelle n'a eu lieu et aucun contrat n'a été conclu entre la famille A._ et la commune. A.d. La procédure de mensuration cadastrale a débuté en 2005. La commune a invité les propriétaires des parcelles concernées à dégager les limites actuelles de leurs biens-fonds et à les piqueter jusqu'au 8 octobre 2005 au plus tard. L'avis communal précisait que " [p]assé le délai prévu, le géomètre, à partir des plans existants (plans cadastraux ou plans d'expropriations) ou avec la commission d'exécution, procédera[it] à la révision du piquetage et complétera[it], au besoin, le piquetage manquant ". A.A._ a indiqué à cet égard avoir effectué le piquetage avec les voisins, mais n'avoir pas pu faire ressortir les points limites sur la route car ceux-ci avaient été recouverts de bitume lors de l'élargissement du chemin; il a par ailleurs ajouté s'être fié au fait que la commune connaissait l'emplacement desdits points limites d'origine et qu'elle ne les modifierait pas. Par courrier du 11 septembre 2006, la commission de mensuration de la commune a avisé les propriétaires concernés que le piquetage et l'abornement étaient achevés et que la détermination des limites était mise à l'enquête publique pendant une période de 30 jours à compter du 18 septembre 2006. Cette même autorité a par ailleurs invité les propriétaires " à consulter les croquis d'abornement et à contrôler l'emplacement des points limites pendant le délai de mise à l'enquête, puisque, celle-ci terminée, tous les points non contestés ser[ai]nt réputés exacts et qu'en cas de contestation ultérieure, tous les frais ser[ai]nt à la charge du recourant ". Une annonce quasi similaire a été insérée par le Département de l'économie et du territoire dans le Bulletin officiel du canton du Valais du 15 septembre 2006. Un " bulletin de propriété " au nom de A.A._ était joint au courrier du 11 septembre 2006. Il laissait apparaître les surfaces suivantes, correspondant à celles figurant jusque-là sur les extraits cadastraux: 612 m2 pour la parcelle no 5422; 253 m2 pour la parcelle no 5423 et 1587 m2 pour la parcelle no 5440. Il n'était en revanche nullement fait mention de la parcelle no 5424 dont A.A._ était pourtant toujours propriétaire en 2006. Le 30 avril 2008, la commune a envoyé à A.A._ la facture pour les travaux de piquetage-abornement, avec en annexe un document laissant apparaître notamment les informations suivantes en relation avec les quatre biens-fonds concernés par la procédure: Parcelle Surface 5422 612 5423 253 5424 292 5440 1587 A nouveau, les surfaces indiquées pour chacun des biens-fonds correspondaient à celles figurant jusque-là sur les extraits du cadastre. A.e. Par courrier du 17 novembre 2010, la commission de mensuration de la commune a transmis à A.A._ un bulletin de propriété, sur lequel était indiqué " la correspondance entre le cadastre communal et la mensuration officielle fédérale "; le courrier précisait par ailleurs que les plans ainsi que le détail des surfaces pouvaient être consultés au cadastre communal, et qu' " une fois l'enquête publique et les réclamations traitées, les nouvelles parcelles ser[aient] introduites au Registre Foncier de Sion ". A.A._ a alors constaté avec surprise que la surface de ses biens-fonds présentait au total une différence de 191 m2 à son détriment par rapport aux surfaces de l'ancien état, et qui peut être représentée au moyen du tableau suivant: No de parcelle État 2006/2008 État 2010 Différence 5422 612 m2 558 m2 - 54 m2 5423 253 m2 223 m2 - 30 m2 5424 292 m2 276 m2 - 16 m2 5440 1587 m2 1496 m2 - 91 m2 Total - 191 m2 A.f. Le chemin F._, en bordure des parcelles nos 5422, 5423 et 5424, a été immatriculé comme immeuble no 7141, et, en bordure de la parcelle no 5440, en tant qu'immeuble no 5925. La route H._, située au sud, porte désormais le no 7139. La commune a précisé ne pas être en mesure de communiquer l'ancien état de ces deux biens-fonds en tant que ces numéros leur avaient été attribués lors de la mensuration. A.g. Par pli du 22 décembre 2010, A.A._ a manifesté son étonnement suite au courrier que la commission de mensuration lui avait adressé le 17 novembre 2010 et à la perte de surface qui résultait de la mensuration officielle, estimant pour l'essentiel que les limites de ses propriétés auraient dû être placées sur la route. Aux termes de son courrier, A.A._ a proposé à la commune de procéder soit au rétablissement de la situation antérieure " au point de vue des m2 avec mention de l'emplacement des limites ", soit à l'achat " du terrain pris pour l'élargissement de ce chemin en route, prix à convenir ". Ces propositions sont restées sans écho. A.h. Le 13 janvier 2011, D._, géomètre au sein de la Société E._ SA, qui était intervenu pour le compte de la commission de mensuration, a adressé un courrier à A.A._, soulignant en substance que les parcelles de celui-ci avaient déjà fait l'objet d'une mise à l'enquête lors de l'abornement des points limites en octobre 2006 - phase à l'issue de laquelle une facture lui avait été envoyée, avec indication des surfaces d'après les extraits cadastraux -, et que la seconde phase - consistant en la mesure exacte des propriétés - aboutissait souvent au constat de l'existence d'un " déficit de surface, car les procédés de mensuration de l'époque ne permettaient pas d'assurer une grande précision ". Après avoir fourni ces explications, le géomètre indiquait qu'il considérait la réclamation de A.A._ comme étant réglée et qu'il appartenait à l'intéressé, s'il n'était pas satisfait, de recourir auprès de l'autorité communale. B. B.a. Par pli expédié le 21 janvier 2011, A.A._ a indiqué maintenir " [s]on recours à l'encontre de ces mensurations ". Statuant le 9 juin 2011, la commission de mensuration de la commune a rejeté la réclamation de l'intéressé au motif que celui-ci n'avait pas contesté l'abornement lors de la mise à l'enquête de sorte qu'il était " trop tard pour invoquer les griefs concernant ces aspects de la procédure ". Le 8 juillet 2011, A.A._ a contesté la décision auprès du juge du district d'Hérens, concluant à ce que " les limites soient remises où elles se trouvaient antérieurement et que le nombre de m2 de [s]es propriétés soit à nouveau calculé ". Le 11 juillet 2011, interprétant l'écriture comme une action en revendication, le juge de district l'a déclarée irrecevable dans la mesure où elle n'avait pas été précédée d'une procédure de conciliation devant le juge de commune et ne respectait par ailleurs pas les exigences de forme prévues par le code de procédure civile suisse. Le 21 septembre 2011, le juge de commune a délivré à A.A._ l'autorisation de procéder. B.b. Avant de porter la cause devant le juge de district, A.A._ a proposé à la commune soit de rectifier les limites, avec octroi contre indemnisation d'une servitude en faveur de la collectivité publique sur l'emprise de la route (1), soit d'acheter du terrain au prix du marché (2), soit de maintenir les limites actuelles mais avec constitution d'une servitude pour la densité et la dérogation de distance et indemnisation pour la " nue-propriété " acquise par la collectivité publique (3). Par courrier du 2 décembre 2011, la commune a fait part de son intention de maintenir sa décision. Le 21 décembre 2011, A.A._ et B.A._ ont ouvert action en revendication contre la commune de U._ devant le juge de district. Leurs conclusions définitives tendaient à ce qu'il soit ordonné à la commune de rétrocéder à A.A._ 91 m2 à détacher de la parcelle du chemin F._ no 7141 et à intégrer à la parcelle no 5440 (1), à ce qu'il lui soit ordonné de rétrocéder à B.A._ 100 m2 à détacher de la parcelle du chemin F._ no 7141 et de celle de la route H._ no 4139 et à intégrer aux parcelles nos 5422, 5423 et 5424 (2), à ce qu'il soit ordonné à la Société E._ SA d'établir un verbal définissant le Nouvel État résultant du jugement ainsi que l'inscription au registre foncier du verbal de mutation définissant la parcelle no 5422 avec une surface de 612 m2, la parcelle no 5423 avec une surface de 253 m2, la parcelle no 5424 avec une surface de 202 m2 et la parcelle no 5440 avec une surface de 1587 m2 (3); à ce qu'il soit ordonné à la Société E._ SA de poser les limites résultant du verbal établi (4). La commune a conclu au rejet de l'action. Une procédure de preuve à futur a été mise en oeuvre à la requête des demandeurs en vue notamment d'effectuer le relevé de l'implantation de la lignée de poiriers plantés sur leurs parcelles, en bordure du chemin F._ et de la route H._. Plusieurs témoins ainsi que A.A._ ont été entendus et une inspection des lieux a été effectuée le 28 juin 2013. Les parties ont renoncé à la mise en oeuvre d'une expertise. Par jugement du 15 novembre 2013, le juge de district a rejeté la demande. Statuant le 23 février 2015 sur l'appel de A.A._ et B.A._, le juge de la Cour civile II du Tribunal cantonal du Valais l'a rejeté, rejetant ainsi la demande formée le 21 décembre 2011 par les intéressés. C. Le 23 mars 2015, A.A._ et B.A._ (les recourants) forment un recours constitutionnel subsidiaire contre cette dernière décision. Reprenant à titre principal les conclusions formulées en instance cantonale, ils réclament à titre subsidiaire le renvoi de la cause au Tribunal cantonal pour nouvelle décision. Les recourants invoquent l'arbitraire dans l'appréciation des preuves et la constatation des faits ainsi que dans l'application du droit; ils soulèvent également la violation de l'art. 26 Cst. Invités à se déterminer, la cour cantonale se réfère à son jugement tandis que l'intimée conclut au rejet du recours. Le recourant a renoncé à répliquer dans le délai imparti, mais s'est exprimé ultérieurement, sans l'intermédiaire de son conseil. L'intimée n'a pas réagi. Le 3 décembre 2015, le Tribunal fédéral a délibéré sur le recours en séance publique. Le dispositif du présent arrêt a été lu à l'issue de la séance.