Faits:
A. A.a Dame A._ et E._ étaient copropriétaires, à raison de la moitié chacun, de la parcelle no 3107 sise sur la commune de F._, au lieu dit "...". Le restaurant H._ loue le bâtiment érigé sur cet immeuble.
La parcelle no 3107 est contiguë à la parcelle no 1. Cette dernière, alors propriété de G._, faisait l'objet, avec le bien-fonds no 4, d'un projet de construction d'un immeuble commercial et d'habitation, baptisé "..." et conçu par le bureau d'architecture C._.
A.b Par acte de radiation et constitution de servitudes du 31 août 1994, dame A._ et E._ ont accepté de grever leur immeuble d'une servitude d'empiètement en faveur de la parcelle no 1, ce afin de permettre la construction d'une dalle de toiture d'une hauteur maximale de 4 m 20, à adosser au bâtiment existant sur la parcelle no 3107. L'assiette de la servitude était dessinée en jaune sur un plan annexé, signé par les parties.
Il était précisé dans l'acte que les propriétaires de la parcelle no 3107 se réservaient la possibilité d'utiliser la surface dont ils étaient propriétaires sur la terrasse à aménager et d'ouvrir des portes d'accès au niveau du premier étage de l'immeuble situé sur leur parcelle. Cet usage était toutefois limité à une portion de la dalle définie en bleu sur le plan.
Le but de la servitude d'empiètement était de permettre de couvrir le passage devant les vitrines de l'immeuble à construire sur la parcelle no 1, tandis que la réserve d'utilisation de la terrasse en faveur du fonds servant devait assurer une issue en cas d'incendie et permettre ainsi l'évacuation des clients du restaurant H._.
La servitude d'empiètement a été dûment inscrite au registre foncier.
Le 25 octobre 1994, C._ a acquis la parcelle no 1.
A.c Début 1996, le bureau C._ a soumis à E._ les plans de l'ouvrage objet de la servitude d'empiètement. E._ a répondu au promoteur qu'il était libre d'aménager la terrasse comme il l'entendait et à ses propres frais.
A.d En 1998, A._, époux de dame A._, a acquis la part de copropriété de E._ sur l'immeuble no 3107.
Le 8 juin 2000, C._ a fait part à A._ de son intention de couvrir l'espace entre les deux immeubles par une marquise en verre translucide. Il a mis à l'enquête publique la construction du bâtiment sis sur les parcelles no 1 et 4 le 10 mai 2002. Les époux A._ n'ont pas formé opposition.
Le 24 septembre 2003, le plan de la marquise et de la couverture du passage situé entre les deux bâtiments a été soumis à A._ pour signature. Celui-ci a refusé de le signer, observant que le projet ne correspondait pas à l'acte passé le 31 août 1994.
Les travaux ont néanmoins débuté. C._ a construit la marquise projetée sur toute la longueur de la servitude d'empiètement. Cet ouvrage n'était toutefois pas conçu pour servir de terrasse depuis le premier étage de l'immeuble érigé sur la parcelle no 3107. De son propre chef, C._ a alors installé une passerelle, destinée à permettre, en cas d'incendie, une issue depuis le premier étage de H._ sur la terrasse de l'immeuble "...".
Le 21 janvier 2004, A._ s'est plaint de la construction de ladite passerelle, sommant le bureau C._ de supprimer cet ouvrage et de remettre la façade en état. Il rappelait également son refus du projet de marquise tel qu'érigé par le bureau d'architecture. Ce dernier lui a répondu qu'il acceptait d'enlever la passerelle si besoin était, lui signalant toutefois que la marquise était conforme à l'acte de servitude signé le 31 août 1994.
A.e Par acte du 10 décembre 2003, C._ a cédé l'immeuble no 1 à D._.
Une fois la construction de l'immeuble "..." achevée, la commune de F._ a enjoint à H._ de se mettre en conformité avec les normes de sécurité et de défense incendie en exécutant une sortie de secours au premier étage.
Par l'intermédiaire de leur mandataire, les époux A._ ont alors exigé la démolition de la marquise et de la passerelle, demandant leur remplacement par la construction d'une dalle résistante, pouvant servir de terrasse et correspondant à la surface dessinée en bleu sur le plan accompagnant l'acte constitutif.
Les parties ne sont toutefois pas parvenues à un accord.
B. B.a Le 10 février 2005, les époux A._ ont cité D._ en conciliation devant le juge de commune de F._. Le 2 mars 2005, D._ a délivré un acte de non-conciliation conventionnel.
B.b Par mémoire-demande du 16 juin 2005, les époux A._ ont ouvert action devant le juge de district de F._ contre D._, devenue ultérieurement B._. Les demandeurs concluaient à ce qu'ordre soit donné à cette dernière d'entreprendre les travaux nécessaires leur permettant d'aménager la terrasse prévue sur les plans annexés à la convention du 31 août 1994, subsidiairement, en cas de non-exécution, de charger une entreprise tierce d'effectuer ces travaux, aux frais de la défenderesse.
C._ est intervenu en cause.
A l'issue de l'instruction, les demandeurs ont précisé leurs conclusions, notamment en ce sens que les travaux soient exécutés conformément aux plans ressortant du rapport d'expertise établi par l'expert X._ et qu'ordre soit donné à B._ de procéder en conséquence à la modification de la servitude au registre foncier de F._. Un délai de six mois dès l'entrée en force du jugement devait en outre être imparti au défendeur pour réaliser les travaux, celui-ci devant, à défaut, s'acquitter en leurs mains d'un montant de 45'000 fr. avec intérêts à 5% dès le 5 février 2005.
B._, de même que C._, ont conclu au rejet de la demande.
La cause a été transmise au Tribunal cantonal du canton du Valais, lequel a rejeté la demande par jugement du 25 février 2010.
C. Par acte du 26 mars 2010, les époux A._ (ci-après les recourants) interjettent un recours en matière civile au Tribunal fédéral, reprenant les conclusions présentées en instance cantonale. A l'appui de celles-ci, ils invoquent la violation des art. 2, 674 et 730 ss CC, plus particulièrement des art. 738 et 741 CC.
Invités à se déterminer, B._ et C._ ont conclu au rejet du recours. La cour cantonale s'est référée aux considérants de sa décision.

Considérant en droit:
1. L'arrêt entrepris est une décision finale (<ref-law>), qui tranche une contestation de nature civile (<ref-law>), portant sur l'aménagement d'une dalle de toiture entre la parcelle appartenant aux recourants et celle dont l'intimée est propriétaire. Il s'agit ainsi d'une affaire de nature pécuniaire, dont la valeur litigieuse atteint 30'000 fr. (art. 74 al. 1 let. b et 51 al. 1 let. a LTF). La décision a par ailleurs été rendue par l'autorité cantonale de dernière instance (<ref-law>) et le recours a été interjeté dans le délai prévu par la loi (<ref-law>), par la partie qui a succombé dans ses conclusions devant l'instance précédente (<ref-law>). Le recours en matière civile est donc en principe recevable.
2. 2.1 La cour cantonale a examiné deux questions:
Elle a avant tout relevé que la servitude d'empiètement accordée le 31 août 1994 par les propriétaires de la parcelle no 3107 au propriétaire de l'article no 1 circonscrivait de façon précise l'ouvrage susceptible d'être construit sur le fonds servant. En tant que l'auvent à ériger devait permettre de supporter une terrasse, il devait ainsi offrir une certaine résistance, de sorte que la construction d'une simple marquise en verre translucide ne correspondait manifestement pas à l'objet de la servitude. Les juges cantonaux en ont conclu que cet ouvrage avait été érigé sans droit sur la propriété des recourants, ceux-ci s'étant au demeurant opposés à une construction de ce type.
Dans un second temps, le Tribunal cantonal a examiné les conclusions des recourants tendant à la constitution d'une dalle avec terrasse. Remarquant que, sauf à être assortie d'une obligation accessoire, une servitude ne pouvait en principe obliger le propriétaire grevé qu'à tolérer ou à s'abstenir, mais non à fournir une prestation, les juges cantonaux ont considéré qu'en l'espèce, si la servitude d'empiètement obligeait les propriétaires grevés à tolérer la construction d'une dalle de toiture sur leur immeuble, elle ne pouvait en revanche leur conférer un droit tendant à l'édification d'un avant-toit résistant. Interprétant ensuite le contrat constitutif de servitude, la cour cantonale en a déduit qu'il appartenait au propriétaire du fonds dominant d'aménager la terrasse, celle-ci devant être en effet intégrée à la marquise qu'il était autorisé à construire, conformément au contrat de servitude. Cette interprétation était d'ailleurs confirmée par l'économie dudit contrat, dont il ressortait que la terrasse devait prioritairement servir les intérêts du propriétaire du fonds dominant. Néanmoins, en tant que l'obligation de construire la terrasse n'avait pas été inscrite au registre foncier, et qu'elle ne remplissait pas les conditions d'une charge foncière, elle n'avait pas d'effet propter rem. Au demeurant, l'obligation de construire la terrasse ne pouvait être qualifiée d'accessoire ni quant à son contenu, ni quant à son étendue: elle ne facilitait en effet en rien l'exercice de la servitude d'empiètement, à savoir la construction de la marquise, mais visait un but différent, soit l'aménagement d'une issue de secours en cas d'incendie, de manière à éviter la construction d'un escalier extérieur. La cour cantonale en a donc conclu que l'obligation de construire la terrasse était une obligation ordinaire, de nature contractuelle, et qu'en tant qu'il n'était nullement établi que l'intimée s'était engagée à reprendre cette obligation à l'égard de C._, elle n'y était donc pas tenue. La demande déposée par les propriétaires du fonds grevé devait en conséquence être rejetée.
2.2 Les recourants soutiennent en substance que le litige n'est pas lié à une quelconque obligation de faire, accessoirement rattachée à la servitude d'empiètement, mais qu'il a trait au contraire au contenu même de celle-ci, que la cour cantonale aurait interprété en violation des <ref-law>. Il ressortirait en effet de l'interprétation du contrat de servitude qu'une fois les travaux conformes à la convention exécutés, les propriétaires de la parcelle grevée pouvaient utiliser la surface située au niveau du premier étage en aménageant une terrasse, et ce sans que des travaux supplémentaires soient entrepris par C._. En tant que la construction érigée par ce dernier n'offrait pas la résistance nécessaire pour supporter ladite terrasse, elle n'était dès lors pas conforme au contenu de la servitude tel que défini par les parties, contenu qui liait néanmoins l'intimée quand bien même celle-ci n'était pas partie au contrat constitutif. Les recourants se prévalent également de l'<ref-law> - selon lequel les frais d'entretien des installations incomberaient au bénéficiaire de la servitude -, soutenant que cette règle s'appliquerait par analogie pour les frais de construction de ces installations.
3. Tant en première instance que dans leur recours au Tribunal fédéral, les recourants concluent à ce que l'intimée soit astreinte à respecter les conditions de la servitude d'empiètement et à construire une dalle de toiture de substitution, les travaux devant être exécutés conformément aux plans figurant dans le rapport d'expertise X._ - à savoir la création d'une terrasse de 1 mètre 75 de largeur sur 8 mètres de longueur correspondant à la partie dessinée en bleu dans le plan annexé à l'acte constitutif.
Alors que les recourants ne demandaient nullement la destruction de la marquise en verre, mais seulement la construction d'une dalle résistante pour la terrasse, la cour cantonale a retenu que la marquise avait été établie sans droit. Puis, bien que le litige opposât les recourants à un tiers acquéreur, dont elle admettait la bonne foi, la juridiction cantonale ne s'est pas fondée sur la volonté objective (cf. notamment <ref-ruling> consid. 3.1 et les réf. citées), mais a recherché la volonté réelle des parties initiales au contrat, retenant que, si C._ s'était engagé à assumer les frais d'aménagement de la terrasse, l'intimée n'avait pas repris cette obligation, qui ne pouvait au demeurant être qualifiée d'obligation accessoire à la servitude.
Seuls les recourants ont toutefois saisi le Tribunal fédéral. Il s'ensuit que la Cour de céans n'a pas à se prononcer sur la motivation cantonale en tant qu'elle excède l'objet du litige et porte sur des questions qui ne sont pas pertinentes.
4.1 4.1.1 En vertu du principe de l'accession, les constructions empiétant sur le fonds voisin (sur le sol ou dans les volumes aérien et souterrain) deviennent propriété du propriétaire de ce fonds (PAUL-HENRI STEINAUER, Les droits réels, tome II, 3e éd., 2002, n. 1647). Pour mettre fin à cette situation inhabituelle, les parties peuvent notamment constituer une servitude d'empiétement (art. 674 al. 1 et 2 CC). Cette servitude, qui possède le caractère d'une servitude foncière (Steinauer, op. cit., n. 1649; HEINZ REY, in Basler Kommentar, 3e éd., 2007, n. 7 ad <ref-law>), a pour effet d'obliger le propriétaire du fonds voisin à tolérer l'empiétement et, au besoin, permet de tenir en échec le principe de l'accession (STEINAUER, op. cit., n. 1649; ARTHUR MEIER-HAYOZ, Berner Kommentar, 3e éd., 1974, n. 36 ad <ref-law>).
La servitude d'empiètement, dont la constitution est régie par les <ref-law>, doit ainsi être inscrite au registre foncier, ce malgré le texte de l'<ref-law> (ATF 78 II 131 consid. 4 p. 137; REY, op. cit., n. 7 ad <ref-law>; STEINAUER, op. cit., n. 1649).
4.1.2 Si les parties sont en principe libres de déterminer le contenu d'une servitude foncière (<ref-law>), leur liberté est néanmoins limitée par la loi: l'<ref-law> rappelle en effet que la servitude ne doit pas consister en une prestation positive à la charge du propriétaire du fonds servant, mais en un devoir de tolérance ou d'abstention, à savoir une attitude passive et non active du propriétaire grevé (cf. <ref-ruling> consid. 2e; PETER Liver, Zürcher Kommentar, 2e éd., 1980, n. 76 ad <ref-law>; Steinauer, op. cit., n. 2205; Hans Michael Riemer, Die beschränkten dinglichen Rechte, 2e éd., 2000, p. 71, n. 18). Le titulaire exerce ainsi sa maîtrise - limitée - sur le fonds grevé sans le concours de son propriétaire, celui-ci étant simplement tenu de respecter le droit réel du titulaire. Il n'y a donc en principe pas de rapport d'obligation entre les deux propriétaires, sous réserve toutefois de deux cas particuliers, à savoir l'obligation accessoire (<ref-law>) et la charge d'entretien (<ref-law>; STEINAUER, op. cit., n. 2278; HEINZ REY, Berner Kommentar, 2e éd., 1981, n. 149 ad <ref-law> [cité: REY, Berner Kommentar]).
Selon l'<ref-law>, une obligation de faire peut en effet être constituée, à titre accessoire, en relation avec une servitude foncière. Cette règle permet ainsi aux parties de prévoir, sans avoir à constituer de charge foncière, que le propriétaire du fonds servant doit faciliter ou assurer l'exercice de la servitude par des prestations positives, généralement liées à l'entretien des ouvrages ou installations nécessaires à l'exercice du droit (Steinauer, op. cit., n. 2219 et les références citées; Liver, op. cit., n. 202 ss et 212 ss ad <ref-law>). L'obligation est accessoire si, par son contenu, elle est destinée à permettre, faciliter ou assurer l'exercice de la servitude et si, par son étendue, elle ne représente pas pour le propriétaire du fonds servant une charge plus lourde que la servitude elle-même (<ref-ruling> consid. 2e; LIVER, op. cit., n. 202 ss ad <ref-law>).
L'<ref-law> prévoit quant à lui que l'entretien des ouvrages nécessaires à l'exercice de la servitude appartient au propriétaire du fonds dominant, la même règle valant pour les frais de construction de ces installations, au moins lorsque celles-ci servent exclusivement à l'exercice de la servitude (STEINAUER, op. cit., n. 2283; LIVER, op. cit., n. 28 ad art. 741). Les règles de l'<ref-law> n'étant pas de droit impératif, les parties peuvent y déroger, soit par exemple en prévoyant une obligation supplémentaire du propriétaire du fonds dominant d'entretenir les ouvrages nécessaires à l'exercice de la servitude, c'est-à-dire une obligation allant au-delà de ce à quoi l'oblige l'<ref-law> (Henri Deschenaux, Le registre foncier, in: Traité de droit privé suisse, volume V, tome II, 2, 1983, p. 558, note 3; Liver, op. cit., n. 67 ss ad <ref-law>; Hans Leemann, Zürcher Kommentar, 1925, n. 2 ad <ref-law>), soit encore en établissant que la charge de l'entretien incombera exclusivement au propriétaire du fonds servant (Steinauer, op. cit., n. 2285; Liver, op. cit., n. 67 ad <ref-law>; Leemann, op. cit., n. 2 ad <ref-law>).
Tant l'obligation accessoire que les devoirs liés à la charge d'entretien constituent des obligations rattachées propter rem au droit de servitude lorsqu'ils sont signalés dans l'inscription au registre foncier (<ref-ruling> consid. 1c; Steinauer, op. cit., n. 2220b; 2283a et 2285a; Rey, Berner Kommentar, n. 155 ss ad <ref-law>; Liver, op. cit., n. 230 ad art. 730 et 73 ss ad <ref-law>; Deschenaux, op. cit., p. 558, note 3; Etienne Petitpierre, in Basler Kommentar, 3e éd., 2007, n. 16 ad <ref-law>). Sous ces deux seules réserves, il n'est cependant pas possible d'intégrer à la servitude foncière elle-même une prestation positive à la charge du propriétaire du fonds servant, respectivement du fonds dominant. Les obligations convenues par les parties dans le cadre de la constitution de la servitude qui n'entrent pas dans la définition de l'obligation accessoire (<ref-law>) ou de la charge d'entretien (<ref-law>) doivent par conséquent être considérées comme des obligations de nature personnelle, qui ne lient que les parties au contrat.
4.2 Aux termes de l'<ref-law>, tout droit dont la constitution est légalement subordonnée à une inscription au registre foncier, n'existe comme droit réel que si cette inscription a eu lieu. Le second alinéa précise que l'étendue d'un droit peut être précisée, dans les limites de l'inscription, par les pièces justificatives ou de toute autre manière. Lex specialis en matière de servitudes, l'<ref-law> reprend cette dernière disposition en prévoyant que l'inscription fait règle en tant qu'elle désigne clairement les droits et les obligations dérivant de la servitude (al. 1). L'étendue de celle-ci peut être précisée, dans les limites de l'inscription, soit par son origine, soit par la manière dont la servitude a été exercée pendant longtemps, paisiblement et de bonne foi (al. 2). Pour déterminer le contenu d'une servitude, il convient ainsi de procéder selon l'ordre des étapes prévu par l'<ref-law>: le juge doit dès lors se reporter en priorité à l'inscription au registre foncier, c'est-à-dire à l'inscription au feuillet du grand livre; ce n'est que si celle-ci est peu claire, incomplète ou sommaire, que la servitude doit être interprétée selon son origine, à savoir l'acte constitutif déposé comme pièce justificative au registre foncier (<ref-ruling> consid. 3.1; <ref-ruling> consid. 2a; arrêt 5C.126/2004 du 21 octobre 2004 consid. 2.3 in RNRF 2005 307; STEINAUER, op. cit., n. 2294). Le contrat de servitude et le plan sur lequel est reportée l'assiette de la servitude constituent à cet égard des pièces justificatives (<ref-law>). Si le titre d'acquisition ne permet pas de déterminer le contenu de la servitude, l'étendue de celle-ci peut alors être précisée par la manière dont elle a été exercée paisiblement et de bonne foi (<ref-law>).
4.3 En l'espèce, la servitude d'empiètement inscrite au registre foncier à charge de l'article 3107, en faveur de la parcelle no 1, impose au propriétaire du fonds grevé de tolérer l'empiètement sur son fonds, permettant au propriétaire du fonds dominant d'être propriétaire des constructions empiétant sur le fonds servant. En tant que l'assiette de l'empiétement ne résulte pas de l'inscription, elle est déterminée, dans les limites de celle-ci, par l'acte constitutif conservé à titre de pièce justificative, conformément aux principes d'interprétation des contrats constitutifs de servitude (consid. 4.2 supra).
Quant à l'obligation de construire une dalle suffisamment solide pour permettre l'aménagement d'une terrasse, que les demandeurs entendent déduire de l'acte constitutif du 31 août 1994 et mettre ainsi à la charge du cocontractant, elle n'est pas une obligation accessoire au sens de l'<ref-law>: elle ne permet en effet nullement de faciliter l'exercice de la servitude d'empiètement et, selon l'interprétation des recourants, elle incomberait au propriétaire du fonds dominant, non au propriétaire du fonds grevé. A l'évidence, cette obligation ne constitue pas non plus une charge supplémentaire d'entretien selon l'<ref-law>, disposition qui, au demeurant, ne saurait en l'espèce être appliquée par analogie dans la mesure où l'obligation projetée ne sert aucunement l'exercice de la servitude d'empiètement accordée.
En définitive, l'éventuelle obligation que les recourants invoquent ne peut être que de nature contractuelle. En tant qu'elle n'a pas été convenue avec l'intimée elle-même, ni ne lui a été transférée, il n'y a toutefois pas lieu de statuer à son sujet, faute de qualité pour défendre de l'intimée.
5. Se fondant enfin sur un courrier du conseil de l'intimée, daté du 3 juin 2004, par lequel ce dernier indiquait que sa cliente n'était pas opposée à l'aménagement de la terrasse litigieuse et que C._ serait disposé à en assumer le coût, les recourants soutiennent qu'en refusant ensuite d'aménager ladite terrasse, l'intimée aurait adopté un comportement contraire à la bonne foi.
Il ressort certes de la constatation des faits cantonaux que le mandataire de l'intimée a indiqué que sa cliente était disposée à ce qu'une terrasse soit aménagée, aux frais de C._. La cour cantonale a toutefois précisé que celui-ci avait déclaré, lors de son audition, qu'il n'était pas disposé à assumer le coût de ces travaux. En tant que les recourants se fondent sur des faits distincts de ceux retenus par l'instance cantonale, sans prendre la peine d'en démontrer l'éventuel arbitraire, il n'y a pas lieu d'entrer en matière sur leur critique.
6. En définitive, le recours est rejeté, dans la mesure de sa recevabilité. Les frais judiciaires sont mis à la charge des recourants qui succombent (<ref-law>). L'intimée, qui s'est déterminée, à droit à une indemnité pour ses dépens (<ref-law>), tandis que C._, intervenant accessoire, conserve les siens (<ref-ruling> consid. 6).

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 à 3'000 fr., sont mis solidairement à la charge des recourants.
3. Une indemnité de 3'000 fr., à payer à l'intimée à titre de dépens, est mise solidairement à la charge des recourants.
4. Le présent arrêt est communiqué aux parties et à la Cour civile II du Tribunal cantonal du canton du Valais.
Lausanne, le 7 juillet 2010
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl de Poret Bortolaso