Faits:
A. A.a Par acte constitutif du 1er juin 1977, inscrit sous PJ 8805-1977, la société C._ SA, propriétaire de l'immeuble no 108 de la commune de D._, a soumis ce dernier au régime de la propriété par étages.
Selon la répartition des parts de propriété par étages établie par l'architecte E._ et mentionnée dans l'acte constitutif, le garage de l'immeuble est désigné sous l'unité d'étage no 8, correspondant au no 11090 du registre foncier. Il représente une quote-part de 58/1000èmes de la parcelle de base. Cette unité d'étage est divisée en 29 places de parc numérotées de A à J (sans I), de A1 à L1 (sans I1) et de A2 à J2 (sans I2), chacune représentant une quote-part de 1/29ème.
A.b Par acte de vente du 2 mai 1981, la société C._ SA a vendu à F._ l'unité d'étage no 11116, représentant une quote-part de 21/1000èmes de la parcelle de base no 108, ainsi qu'une quote-part de 1/29ème de la PPE no 11090 (parking no 8). L'acte de vente précise expressément "Jouissance exclusive de la place de parc désignée sous lettre 'B1' du plan, au deuxième sous-sol".
Les 1er et 8 septembre 1981, l'Association G._ a notamment acquis de la société C._ SA deux quotes-parts de la PPE no 11090 (parking no 8). Le premier acte de vente mentionne expressément la place de parc no A1, tandis que le second a la teneur suivante: "PPE 11090 - 58/1000èmes du no 108 plan no 4 - droit exclusif sur parking no 8 - 1er, 2ème, 3ème sous-sol - soit 1/29ème de cette PPE (place lettre B1)".
Par "convention d'apport en nature et reprise de biens" du 7 novembre 1994, G._ a notamment cédé à la société Y._ SA les 2/29èmes de la PPE 11090 acquis en septembre 1981. Cet acte ne précise pas à quelles places du parking no 8 ces parts correspondent. Différents témoignages ont néanmoins permis de retenir, sans qu'aucun acte du dossier ne les mette en doute, que, dès 1981 et indépendamment de l'acte de cession précité, ce sont toujours les actionnaires de Y._ SA, également sociétaires de G._, qui ont utilisé la place de parc B1.
Le 23 août 2007, les époux X._ ont acheté à F._ l'unité d'étage no 11116 ainsi qu'une quote-part de 1/29ème de l'unité d'étage no 11090. Au sujet de cette dernière, l'acte de vente mentionne: "ce 1/29ème donn(e) droit à la place B1 selon acte de vente de 1981 et selon acte constitutif de PPE d'origine".
A.c Par courrier du 7 décembre 2007, les époux X._ ont indiqué à l'administrateur de la communauté des propriétaires d'étages de l'immeuble no 108 qu'il devait y avoir une erreur dans la distribution des places de parc, la place qui leur avait été attribuée l'ayant été également à la société Y._ SA. Ils lui demandaient ainsi de trouver une solution à ce différend.
L'administrateur a mandaté Me H._, avocat et notaire, afin qu'il examine la situation. Dans le rapport qu'il a établi le 19 décembre 2007, le mandataire observe que certaines places de parc avaient été vendues deux fois, que certaines attributions restaient obscures, que des places de parc, dont la référence ne correspondait pas au plan de l'architecte, avaient été octroyées à certains copropriétaires et qu'enfin, différentes places de parc attribuées à des copropriétaires avaient été transformées en local à skis commun.
Le 22 février 2008, afin de régulariser la situation, l'administrateur a adressé aux propriétaires d'étages un courrier leur proposant une réattribution des places de parc. Selon cette proposition, les places A1 et B1 étaient octroyées à la société Y._ SA tandis que les époux X._ se voyaient attribuer la place G1.
Tous les propriétaires intéressés ont adhéré à ladite proposition, à l'exception des époux X._, ces derniers s'y opposant par courrier du 18 mars 2008. Le 5 mai 2008, ils ont mis en demeure la société Y._ SA de ne plus utiliser la place de parc no B1; la société n'ayant pas donné suite à leur injonction, ils lui ont adressé un ultime délai au 15 septembre 2008, l'informant qu'à défaut de réaction, ils saisiraient les autorités judiciaires compétentes.
B. Par demande déposée devant le Tribunal cantonal du canton du Valais le 1er décembre 2008, les époux X._ ont ouvert action en cessation de trouble et en rectification du registre foncier contre la société Y._ SA. Ils ont conclu à ce qu'il soit constaté qu'ils étaient seuls propriétaires de la place de parc B1, à ce qu'il soit fait interdiction à la société défenderesse d'utiliser de quelque manière que ce soit ladite place de parc, sous commination des suites légales en cas de violation de ladite interdiction et à la rectification du registre foncier de I._ en conséquence.
La société défenderesse a conclu au rejet de la demande.
Après avoir instruit la cause, la juge III du district de Sierre a transmis le dossier au Tribunal cantonal pour jugement le 27 mai 2010.
Le 29 novembre 2010, cette dernière juridiction a rejeté la demande, dans la mesure de sa recevabilité.
C. Le 17 janvier 2011, A.X._ et B.X._ (ci-après les recourants) interjettent un recours en matière civile devant le Tribunal fédéral contre la décision cantonale. Ils concluent à l'annulation de celle-ci et, reprennent, à titre principal, les conclusions prises en instance cantonale, à l'exception de leur conclusion constatatoire. Subsidiairement, ils demandent le renvoi de la cause à l'autorité cantonale.
Des observations n'ont pas été demandées.

Considérant en droit:
1. Le recours est dirigé contre une décision finale (<ref-law>), rendue en matière civile (<ref-law>); il est interjeté par la partie qui a succombé dans ses conclusions devant l'instance précédente (<ref-law>), dans le délai prévu par la loi (art. 46 al. 1 let. c et 100 al. 1 LTF).
L'autorité cantonale a fixé la valeur litigieuse à 40'000 fr., de sorte que le seuil de 30'000 fr. prévu par l'<ref-law> est atteint.
L'arrêt du Tribunal cantonal ayant été rendu et expédié aux parties en 2010, il n'est pas soumis au code de procédure civile fédéral du 19 décembre 2008 (CPC; RS 272), entré en vigueur le 1er janvier 2011 (<ref-ruling> consid. 2). Le droit transitoire relatif aux art. 75 al. 2 et 111 al. 3 LTF, tel que prévu par l'<ref-law>, demeure donc applicable au présent recours. Celui-ci, dirigé contre un arrêt du Tribunal cantonal du canton du Valais statuant en instance unique, est dès lors ouvert.
2. 2.1 Le recours en matière civile peut être formé pour violation du droit fédéral (<ref-law>). Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour d'autres motifs que ceux qui ont été invoqués et le rejeter en adoptant une argumentation différente de celle de l'autorité précédente (cf. <ref-ruling> consid. 1.1).
2.2 Le Tribunal fédéral ne peut s'écarter des faits établis par l'autorité précédente que si ceux-ci ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>) et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>). Le recourant qui soutient que les faits ont été établis d'une manière manifestement inexacte (<ref-law>), à savoir arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.4.1 p. 39; <ref-ruling> consid. 1.2.2 p. 252), doit satisfaire au principe d'allégation (<ref-ruling> consid. 3.2 et les arrêts cités). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 2 p. 591/592 et les arrêts cités).
3. La cour cantonale a jugé que le parking devait être considéré, dans son entier, comme une unité d'étage, détenue par les propriétaires d'étages concernés en copropriété ordinaire. Conformément à l'<ref-law>, les recourants ne pouvaient dès lors prétendre être seuls propriétaires d'une part déterminée de ce parking. Ils ne pouvaient pas non plus se prévaloir d'un droit de propriété sur la place de parc litigieuse car les places de parc, prises individuellement, n'étaient pas des immeubles au sens de l'<ref-law> et ne pouvaient être ainsi l'objet d'un droit de propriété exclusive. Seul un droit dit "d'usage particulier" entrait en considération.
Ce principe étant posé, le tribunal cantonal a rejeté la demande pour trois motifs.
Se référant d'abord à l'art. 8 du règlement d'administration et d'utilisation, les juges cantonaux ont observé que le droit d'usage particulier ne pouvait être octroyé que par l'assemblée des propriétaires d'étages, de sorte que la société C._ SA n'avait pu le céder valablement. Néanmoins, jusqu'à la survenance du présent litige, l'usage des places de parc du garage collectif faisait l'objet d'un consensus entre l'ensemble des copropriétaires: la société intimée utilisait ainsi la place de parc litigieuse, sans que les autres copropriétaires s'en plaignissent. Une telle pratique, respectée de manière constante et admise par tous depuis près de 30 ans, devait dès lors être qualifiée de règlement régissant la répartition de l'utilisation de la chose au sens de l'<ref-law>. En tant que la loi n'exigeait pas la forme écrite pour l'édiction d'un tel règlement, il s'imposait par conséquent à tous les copropriétaires de l'unité d'étage en vertu des dispositions de l'<ref-law>.
Relevant ensuite l'existence d'échanges informels entre certains copropriétaires, la cour cantonale a estimé qu'il était dès lors concevable que, entre le 2 mai et le 8 septembre 1981 - date des ventes opérées entre C._ SA et F._, respectivement G._ -, un tel échange soit intervenu entre F._ et la société C._ SA, raison pour laquelle cette dernière avait estimé être en mesure de conférer à G._ le droit d'usage particulier sur la place de parc litigieuse. Le fait que F._ n'eût jamais revendiqué l'usage de celle-ci durant plus de 26 ans rendait cette hypothèse crédible.
Enfin et subsidiairement, les juges cantonaux ont considéré qu'à défaut d'avoir été introduite contre l'ensemble des autres copropriétaires de l'unité d'étage concernée, la demande devait être rejetée pour défaut de qualité pour défendre.
4. 4.1 Les recourants invoquent la violation de différentes dispositions légales sur la portée du principe de publicité du registre foncier (<ref-law>) ainsi que sur les effets de l'inscription à ce dernier (art. 973 et 974 CC). Pour l'essentiel, leur motivation consiste à soutenir que l'objet de l'acte de vente conclu le 2 mai 1981 entre F._ et la société C._ SA - notamment le droit à la jouissance exclusive d'une place de parc, expressément désignée sous la lettre B1 - ressortirait du registre foncier. Ils s'y seraient fiés de bonne foi et pensaient ainsi acquérir la jouissance exclusive de ladite place en concluant le contrat de vente avec F._. Conformément à l'<ref-law>, leur bonne foi devait dès lors être protégée et ils devaient être maintenus dans leur acquisition. Les recourants paraissent ensuite soutenir que les prétendus droits de l'intimée sur la place B1 auraient été inscrits ultérieurement aux leurs (principe de la priorité dans le temps) et que, dans la mesure où nul ne peut se prévaloir de ce qu'il n'a pas connu une inscription au registre foncier (principe de publicité; art. 970 al. 3 [recte: 4] CC), l'intimée ne serait pas de bonne foi et ne pouvait dès lors se fonder sur l'<ref-law> pour se prévaloir d'un droit sur la place litigieuse; bien plus, ils pouvaient lui opposer l'<ref-law>. Les recourants en concluent que l'<ref-law> leur permettrait de réclamer la radiation de l'intimée en tant que propriétaire de la place de parc litigieuse.
4. 4.1 Les recourants invoquent la violation de différentes dispositions légales sur la portée du principe de publicité du registre foncier (<ref-law>) ainsi que sur les effets de l'inscription à ce dernier (art. 973 et 974 CC). Pour l'essentiel, leur motivation consiste à soutenir que l'objet de l'acte de vente conclu le 2 mai 1981 entre F._ et la société C._ SA - notamment le droit à la jouissance exclusive d'une place de parc, expressément désignée sous la lettre B1 - ressortirait du registre foncier. Ils s'y seraient fiés de bonne foi et pensaient ainsi acquérir la jouissance exclusive de ladite place en concluant le contrat de vente avec F._. Conformément à l'<ref-law>, leur bonne foi devait dès lors être protégée et ils devaient être maintenus dans leur acquisition. Les recourants paraissent ensuite soutenir que les prétendus droits de l'intimée sur la place B1 auraient été inscrits ultérieurement aux leurs (principe de la priorité dans le temps) et que, dans la mesure où nul ne peut se prévaloir de ce qu'il n'a pas connu une inscription au registre foncier (principe de publicité; art. 970 al. 3 [recte: 4] CC), l'intimée ne serait pas de bonne foi et ne pouvait dès lors se fonder sur l'<ref-law> pour se prévaloir d'un droit sur la place litigieuse; bien plus, ils pouvaient lui opposer l'<ref-law>. Les recourants en concluent que l'<ref-law> leur permettrait de réclamer la radiation de l'intimée en tant que propriétaire de la place de parc litigieuse.
4.2 4.2.1 Ainsi que l'a relevé la cour cantonale, il est envisageable de constituer un garage collectif en une unité d'étage détenue par les propriétaires d'étages en copropriété ordinaire. La qualité de copropriétaire peut être attribuée aux propriétaires d'étages nommément, mais elle peut également être rattachée aux parts d'étages elles-mêmes: on parle alors de copropriété dépendante (AMEDEO WERMELINGER, La propriété par étages, 2e éd. 2008, n. 20 et 24 ad <ref-law>; cf. également ARTHUR MEIER-HAYOZ/HEINZ REY, Berner Kommentar, 1988, n. 56 ad <ref-law>; PAUL-HENRI STEINAUER, Questions choisies en rapport avec la propriété par étages, in Revue valaisanne de jurisprudence [RVJ] 1991 p. 285 ss, p. 294; PASCAL SIMONIUS/THOMAS SUTTER, Schweizerisches Immobiliarsachenrecht, tome I, 1995, p. 522 n. 19; DIETER ZOBL, Rechtsfragen zur Sondernutzung an Autoabstellplätzen bei Stockwerkeigentum, in Mélanges en l'honneur de Jacques-Michel Grossen, 1992, p. 285 ss, p. 286 s.; MARTIN HABS, La propriété par étages sur des maisons familiales en habitat groupé, 1989, p. 127).
Il ressort en l'espèce de l'extrait du registre foncier que le garage collectif est une unité d'étage de la propriété par étages et qu'elle appartient en copropriété ordinaire indépendante aux propriétaires actuels des parts d'étages, tous nommément désignés. Le droit d'user exclusivement une place de parc déterminée ne ressort ni du registre foncier, ni des plans qui y sont déposés. Il s'ensuit que les griefs des recourants relatifs à la violation des art. 970, 973 et 974 CC sont infondés.
5.1 5.1.1 L'utilisation et l'administration d'une part d'étage détenue en copropriété - comme en l'espèce le parking - sont définies par le règlement interne à la copropriété et non par celui de la propriété par étages. Ce règlement d'utilisation et d'administration (<ref-law>) doit être pris dans le cadre d'une assemblée des copropriétaires, qui prend ses décisions conformément au régime de la copropriété et qui dispose de ses propres droits de participation et de vote dans celui de la propriété par étages (arrêt 5A_364/2011 du 8 juillet 2011 consid. 3.1; cf. AMEDEO WERMELINGER, Zürcher Kommentar, 2010, n. 29 ad <ref-law>).
Par le biais du règlement d'utilisation et d'administration, les copropriétaires peuvent notamment prévoir le rattachement d'un droit préférentiel (Vorrecht) à certaines quotes-parts, droit qui permet aux copropriétaires concernés d'administrer, d'utiliser et de jouir exclusivement d'espaces déterminés du bâtiment ou des surfaces détenus en copropriété. Il en résulte une distinction entre les parties qui sont objets de droits préférentiels de celles qui demeurent communes (CHRISTOPH LÜSCHER, Voraussetzungen und Schranken der Angleichung von schlichtem Miteigentum an Stockwerkeigentum hinsichtlich Nutzung, Verwaltung und Innenausbau des gemeinschaftlichen Gebäudes, in Revue du notariat et du registre foncier [RNRF] p. 73 ss, p. 76 et les références citées; MEIER-HAYOZ, Berner Kommentar, 5e éd. 1981, n. 42 ad <ref-law>). Chaque copropriétaire peut ainsi se voir attribuer le droit préférentiel d'utiliser exclusivement une place de stationnement déterminée dans un garage collectif, les espaces non attribués restant communs.
5.1.2 A l'instar du droit d'usage particulier, qui confère au propriétaire d'étages un droit d'utilisation sur une partie commune (<ref-ruling> consid. 4b; WERMELINGER, op. cit., n. 151, p. 104), le droit préférentiel est un droit personnel (LÜSCHER, op. cit., p. 77). Il produit néanmoins certains effets caractéristiques des droits réels dans la mesure où le copropriétaire, empêché ou gêné par un autre dans l'exercice de son droit préférentiel, est troublé dans sa propriété (LÜSCHER, op. cit., p. 79; cf. également SIMONIUS/SUTTER, op. cit., p. 481, n. 43). Il dispose ainsi des actions pétitoires et possessoires, de même que des actions en dommages-intérêts ou en enrichissement illégitime (CHRISTOPH BRUNNER/JÜRG WICHTERMANN, Basler Kommentar, 3e éd. 2007, n. 18 ad <ref-law>).
5.1.2 A l'instar du droit d'usage particulier, qui confère au propriétaire d'étages un droit d'utilisation sur une partie commune (<ref-ruling> consid. 4b; WERMELINGER, op. cit., n. 151, p. 104), le droit préférentiel est un droit personnel (LÜSCHER, op. cit., p. 77). Il produit néanmoins certains effets caractéristiques des droits réels dans la mesure où le copropriétaire, empêché ou gêné par un autre dans l'exercice de son droit préférentiel, est troublé dans sa propriété (LÜSCHER, op. cit., p. 79; cf. également SIMONIUS/SUTTER, op. cit., p. 481, n. 43). Il dispose ainsi des actions pétitoires et possessoires, de même que des actions en dommages-intérêts ou en enrichissement illégitime (CHRISTOPH BRUNNER/JÜRG WICHTERMANN, Basler Kommentar, 3e éd. 2007, n. 18 ad <ref-law>).
5.2 5.2.1 Le règlement d'utilisation et d'administration établi par les copropriétaires constitue un contrat, qui présente des caractéristiques propres aux contrats de sociétés (MEIER-HAYOZ, op. cit., n. 37 ad <ref-law>; BRUNNER/WICHTERMANN, op. cit., n. 22 ad <ref-law>; LÜSCHER, op. cit., p. 77 et les références citées; cf. <ref-ruling> consid. 3). Lorsqu'il attribue des droits préférentiels, il détermine ainsi les relations réciproques des copropriétaires entre eux pour la durée de la copropriété (LÜSCHER, op. cit., p. 77).
Le règlement d'utilisation et d'administration doit être approuvé à l'unanimité des copropriétaires (<ref-ruling> consid. 3; MEIER-HAYOZ, op. cit., n. 37 ad <ref-law>; BRUNNER/WICHTERMANN, op. cit., n. 22 ad <ref-law>). S'il n'est pas soumis à une forme particulière, il doit toutefois revêtir la forme écrite si les copropriétaires souhaitent le mentionner au registre foncier (art. 79 al. 4 de l'ordonnance sur le registre foncier [ORF; RS 211.432.1]; arrêt 4C.388/2005 du 20 février 2006 consid. 2.3.3; MEIER-HAYOZ, op. cit., n. 40 ad <ref-law>; BRUNNER/WICHTERMANN, op. cit.,n. 25 ad <ref-law>).
5.2.2 Selon l'<ref-law>, pour apprécier la forme et les clauses d'un contrat, il y a lieu de rechercher la réelle et commune intention des parties, sans s'arrêter aux expressions ou dénominations inexactes dont elles ont pu se servir, soit par erreur, soit pour déguiser la nature véritable de la convention. Le juge doit rechercher, dans un premier temps, la réelle et commune intention des parties (interprétation subjective), le cas échéant empiriquement, sur la base d'indices. Les circonstances survenues postérieurement à la conclusion du contrat, notamment le comportement des parties, constituent un indice de leur volonté réelle et doivent donc être prises en considération dans l'interprétation subjective (<ref-ruling> consid. 4c; <ref-ruling> consid. 1; <ref-ruling> consid. 4a; <ref-ruling> consid. 6 p. 418). Si elle aboutit, cette démarche conduit à une constatation de fait (<ref-ruling> consid. 3.1 p. 667). Ce n'est que s'il ne parvient pas à déterminer cette volonté réelle ou s'il constate qu'une partie n'a pas compris la volonté manifestée par l'autre, que le juge doit découvrir quel sens les parties pouvaient ou devaient donner, de bonne foi, à leurs manifestations de volonté réciproques (principe de la confiance), c'est-à-dire rechercher leur volonté objective, question de droit que le Tribunal fédéral revoit librement (parmi plusieurs: <ref-ruling> consid. 3.2; <ref-ruling> consid. 3.3; <ref-ruling> consid. 2.3.2, 626 consid. 3.1).
5.3 Il n'existe en l'espèce aucun règlement d'utilisation et d'administration et donc de contrat écrit relatif au parking détenu en copropriété ordinaire par les propriétaires des différentes parts d'étages. L'existence d'un tel règlement, et celle d'un droit préférentiel sur la place litigieuse, peuvent toutefois être déduites par interprétation subjective, en se fondant sur le comportement adopté par G._ et F._ suite à l'acquisition de leurs quotes-parts respectives. Il résulte en effet des témoignages apportés en cours de procédure - que les recourants ne critiquent pas - que la première utilisait la place de stationnement litigieuse, sans que cette utilisation ne soit contestée par la seconde et les autres copropriétaires. Jusqu'en 2007, la société intimée a poursuivi cet usage sans opposition.
Le témoignage de Me H._, invoqué par les recourants pour nier l'existence d'un consensus général quant à l'attribution de l'ensemble des places de parc, est sans pertinence en tant que seule l'utilisation de la place B1 fait l'objet du présent litige. C'est ainsi l'existence d'un consensus à propos de cette seule place qui importe. A cet égard, le témoignage invoqué répond d'ailleurs par l'affirmative. Il s'ensuit donc que les recourants ne disposent d'aucun droit préférentiel sur celle-ci.
6. Le sort du litige étant scellé par le considérant précédent, il n'y a pas lieu d'examiner les critiques des recourants relatives aux motivations cantonales subsidiaires (<ref-ruling> consid. 6; <ref-ruling> consid. 6a).
7. En conclusion, le recours doit être rejeté, aux frais de ses auteurs qui répondront solidairement (art. 66 al. 1 et 5 LTF). Aucune indemnité de dépens n'est octroyée à l'intimée qui n'a pas été invitée à répondre.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 3'500 fr., sont mis solidairement à la charge des recourants.
3. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Cour civile II.
Lausanne, le 27 juillet 2011
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Hohl
La Greffière: de Poret Bortolaso