Faits:
A. A.a F._, né en 1926, a rencontré de graves problèmes de santé au cours de l'été 1999. Par décision du 20 janvier 2000, la Chambre pupillaire de G._ a prononcé une mesure de conseil légal gérant et coopérant en sa faveur et nommé sa troisième épouse, E._, en qualité de conseil légal.
A.b F._ est décédé le 10 juillet 2002 à G._, laissant pour héritiers ses enfants A._, B._, C._, nés de sa première union, D._, né de son deuxième mariage, et E._ son épouse.
A.c Par testament olographe du 14 septembre 1995, F._ a notamment pris les dispositions pour cause de mort suivantes :
"II. J'institue comme mon héritière universelle, mon épouse E._.
III. J'entends exhéréder, pour les raisons qui suivent, mes quatre enfants, tous majeurs. Si cette disposition, mûrement réfléchie, ne devait pas être interprétée comme conforme aux exigences légales, elle vaudrait pour les ramener à leur plus stricte réserve."
B. B.a Le 4 juillet 2003, A._, B._, C._ et D._ ont ouvert action contre E._ en nullité du testament, en partage et en reddition de comptes, subsidiairement en réduction, en partage et en reddition de comptes, devant la IIe Cour civile du Tribunal cantonal du canton du Valais.
Par exploit du 27 juin 2005, les demandeurs ont retiré leurs conclusions principales, leurs conclusions subsidiaires devenant principales.
Par nouvel exploit du 22 octobre 2010, les demandeurs ont modifié leurs conclusions de la manière suivante:
"1. Il est constaté que l'exhérédation prévue dans le testament du 14 septembre 1995 à l'égard de A._, C._, D._ et B._ n'est pas valable.
2. Il est constaté que A._, C._, D._ et B._ ont la qualité d'héritiers réservataires au sens de l'art. 471 ch. 1 CC.
3. L'action en réduction est admise et E._ est condamnée à payer à chacun des héritiers le montant correspondant à leur réserve après composition et estimation de la masse successorale à établir après la reddition des comptes et l'approbation de comptes par la Chambre pupillaire de G._.
4. E._ est condamnée à la reddition des comptes et à remettre aux demandeurs toutes les pièces ou documents bancaires et autres se rapportant à la gestion des affaires de F._.
5. E._ est condamnée à communiquer toutes les libéralités entre vifs dont elle a bénéficié.
6. Les frais et dépens sont mis à la charge de E._."
L'intimée a conclu principalement au rejet de l'action, subsidiairement, en cas d'admission de l'action en réduction, à ce que les demandeurs aient "droit à leur part réservataire de la masse successorale à partager, composée exclusivement des biens désignés dans l'inventaire du Juge de la Commune de G._ du 9 octobre 2002, sous déduction du passif de la succession".
B.b Par jugement du 22 novembre 2010, la IIe Cour civile du Tribunal cantonal du canton du Valais a admis l'action en réduction, constaté que A._, B._, C._ et D._ sont les héritiers réservataires du défunt et ont droit chacun à 3/32èmes de la succession de leur père (1.); pour le reste, elle a rejeté l'action (2.). L'autorité cantonale a réparti les frais pour un tiers à charge des demandeurs solidairement entre eux et pour deux tiers à charge de l'intimée, "chaque partie supportant ses propres frais d'intervention" (3.).
C. Par acte du 10 janvier 2011, les demandeurs ont interjeté un recours constitutionnel subsidiaire au Tribunal fédéral. Ils concluent à l'annulation partielle du chiffre 3 du dispositif du jugement de la IIe Cour civile du Tribunal cantonal du canton du Valais et au renvoi de la cause à l'autorité cantonale pour nouvelle décision.
Invitées à se déterminer, l'intimée conclut au rejet du recours, alors que l'autorité cantonale se réfère aux considérants de son jugement.
Considérant en droit:
1. L'unique point litigieux en instance fédérale porte sur la répartition des dépens de la procédure cantonale. En vertu du principe de l'unité de la procédure, la voie de recours ouverte contre une telle décision est déterminée par l'objet du litige principal (ATF 134 V 138 consid. 3 p. 144; pour les frais de justice: ATF 134 I 159 consid. 1.1 p. 160), qui est, en l'espèce, de nature successorale (art. 72 al. 1 LTF).
Le montant des dépens ne doit pas être pris en considération pour le calcul de la valeur litigieuse (art. 51 al. 3 LTF). Partant, la voie du recours en matière civile est ouverte lorsque les conclusions sur le fond encore en cause devant l'autorité précédente atteignaient la valeur litigieuse minimale (art. 74 al. 1 let. b LTF), même si les dépens faisant l'objet exclusif du recours restent au-dessous de cette valeur (ATF 137 III 47 consid. 1.2.3 p. 48). A cet égard, il ressort du jugement entrepris que "les demandeurs sollicitent, notamment, l'admission de leur action en réduction, alors que la défenderesse conclut au rejet de cette prétention. A teneur de la décision du 2 mai 2005 rendue par le juge chargé de l'instruction, la part réservataire globale des demandeurs peut être évaluée à plus de 500'000 fr.".
L'autorité cantonale a expédié son jugement aux parties le 23 novembre 2010. Celles-ci l'ont reçu le lendemain 24 novembre 2010. En vertu de l'art. 46 al. 1 let. c LTF, les délais de recours fixés en jours par la loi ne courent pas du 18 décembre au 2 janvier inclus (arrêt 2C_174/2008 du 29 février 2008 consid. 2.1). Le recours est ainsi exercé en temps utile (art. 100 al. 1 LTF) à l'encontre d'une décision finale (art. 90 LTF) prise en instance cantonale unique (art. 75 al. 2 let. c LTF). Les recourants ont qualité pour agir (art. 76 al. 1 LTF).
Il s'ensuit que le recours en matière civile est recevable, si bien que la voie du recours constitutionnel subsidiaire choisie par les recourants est fermée (art. 113 LTF). L'acte déposé par les recourants sera donc traité comme un recours en matière civile.
2. Les questions relatives à l'allocation des dépens dans les procès relevant des juridictions cantonales sont réglées par le droit cantonal (arrêt 5P.499/1993 du 5 septembre 1994 consid. 3a). Sauf dans les cas cités expressément par l'art. 95 LTF, le recours en matière civile ne peut pas être formé pour violation du droit cantonal en tant que tel. En revanche, il est toujours possible de faire valoir que la mauvaise application du droit cantonal constitue une violation du droit fédéral, en particulier qu'elle est arbitraire au sens de l'art. 9 Cst. (ATF 133 III 462 consid. 2.3 p. 466; ATF 134 III 379 consid. 1.1 p. 382-383). Dans ce cas, le recourant doit désigner la norme cantonale qui aurait été violée arbitrairement et exposer en quoi consiste cette violation (art. 106 al. 2 LTF; ATF 118 Ia 112 consid. 2c p. 118; ATF 133 II 396 consid. 3.1 p. 399; BERNARD CORBOZ, Commentaire de la LTF, 2009, n° 40 ad art. 106 LTF).
En matière d'interprétation et d'application du droit cantonal, il ne faut pas confondre arbitraire et violation de la loi. Une violation doit être manifeste et reconnue d'emblée pour être considérée comme arbitraire. Le Tribunal fédéral n'a pas à examiner quelle est l'interprétation correcte que l'autorité cantonale aurait dû donner des dispositions applicables; il doit uniquement se prononcer sur le caractère défendable de l'application ou de l'interprétation qui en a été faite. Il n'y a pas arbitraire parce qu'une autre solution paraît également concevable, voire préférable (ATF 133 III 462 consid. 4.4.1 p. 470; ATF 132 I 13 consid. 5.1 p. 18; ATF 131 I 217 consid. 2.1 p. 219).
2.1 Les recourants font grief à l'autorité cantonale d'avoir fait preuve d'arbitraire (art. 9 Cst.) dans l'application des normes de la procédure civile valaisanne en relation avec l'allocation des dépens (recours p. 4 ch. 5). Ils soutiennent que l'art. 260 al. 1 du Code de procédure civile du 24 mars 1998 (ci-après: CPC/VS) s'interprète à la lumière de l'art. 252 CPC/VS relatif aux frais. En conséquence, l'autorité cantonale aurait dû statuer sur le sort des dépens en procédant à une répartition dans la même proportion que pour les frais.
La partie intimée fait valoir que les critères relatifs à la répartition des frais prévus par l'art. 11 de la loi valaisanne fixant le tarif des frais et dépens devant les autorités judiciaires ou administratives du 14 mai 1998 (ci-après: LTar/VS) sont différents de ceux concernant les dépens (art. 26 LTar/VS).
2.2 L'art. 260 CPC/VS ne mentionne les dépens que pour préciser que l'indemnité due à ce titre est à la charge de la partie condamnée aux frais, mais ne règle pas le problème de leur répartition. Quant à elle, la question du sort des dépens est réglée par la LTar/VS (MICHEL DUCROT, Le droit judiciaire valaisan, 2000, p. 182), non invoquée par les recourants (art. 106 al. 2 LTF; cf. supra consid. 2). Selon l'art. 30 al. 1 LTar/VS, "[a]u terme de toute procédure, l'ampleur et le sort des dépens sont en principe arrêtés dans le jugement ou la décision". S'agissant des dépens, l'art. 30 al. 3 LTar/VS dispose encore ce qui suit: "L'autorité fixe les honoraires en chiffres ronds en se conformant, pour le surplus, aux dispositions spéciales des diverses lois de procédure". Enfin, l'art. 32 LTar/VS détermine, sur la base de la valeur litigieuse, les honoraires minimaux et maximaux dus à l'avocat notamment pour les contestations civiles de nature pécuniaire tranchées en instance cantonale unique.
2.3 Lorsque sa cognition est restreinte à l'arbitraire, le Tribunal fédéral ne s'écarte de la solution retenue par l'autorité précédente que si celle-ci apparaît insoutenable (cf. supra consid. 2). Or, comme on l'a vu (cf. supra consid. 2.2), le seul texte de l'art. 260 CPC/VS ne permet nullement d'affirmer que l'art. 252 CPC/VS relatif aux frais s'appliquerait mutatis mutandis aux dépens et que, partant, il imposerait une clé de répartition identique pour les frais et pour les dépens. Cette solution est par ailleurs confortée par l'interprétation systématique de la LTar/VS dont il résulte que la question des frais et celle des dépens font l'objet de deux chapitres distincts.
La loi cantonale réserve en outre une large marge d'appréciation au juge concernant le sort des frais puisqu'elle prévoit la possibilité de déroger au principe général (art. 252 al. 1 et 2, 1ère phrase, CPC/VS; MICHEL DUCROT, op. cit., p. 182; OLIVIER DERIVAZ, Les frais et dépens, les sûretés et l'assistance judiciaire, in Le nouveau droit judiciaire privé valaisan, 1998, n° 1.3.2 p. 5 et n° 2.2.3 in fine p. 11). Selon la doctrine, la latitude en matière de dépens ne serait pas aussi étendue que celle prévue à l'art. 252 CPC/VS (OLIVIER DERIVAZ, op. cit., n° 3.2.2 p. 15), ce qui a pour conséquence que la répartition des frais et des dépens peut être différente pour une même cause. Tel est le cas en l'espèce. L'autorité cantonale a apprécié les circonstances puis réparti les frais de justice entre les parties sur la base du raisonnement qu'elle expose au considérant 15 de son jugement (p. 47/48). S'agissant en revanche des dépens, les juges précédents ne se sont pas écartés du principe du résultat ("Erfolgsprinzip"; MICHEL DUCROT, op. cit., p. 181). Il ressort du jugement cantonal que les recourants ont certes obtenu gain de cause sur l'objet principal du litige, mais qu'ils ont succombé pour le surplus après avoir retiré puis modifié leurs conclusions en cours d'instance. L'intimée a également obtenu partiellement gain de cause en ce qui concerne la conclusion reconventionnelle qu'elle avait prise à titre subsidiaire. Les parties ayant chacune vu une part de leurs conclusions admise, la compensation des dépens retenue par l'autorité précédente ne consacre aucun abus du pouvoir d'appréciation qui relèverait de l'arbitraire.
3. En conclusion, le recours doit être rejeté. Les frais judiciaires sont mis solidairement à la charge des recourants, qui succombent (art. 66 al. 1 et 5 LTF). Il en va de même de l'indemnité de dépens à payer à l'intimée, qui s'est déterminée sur le fond de la cause (art. 68 al. 1, 2 et 4 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 5'000 fr., sont mis solidairement à la charge des recourants.
3. Une indemnité de 5'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 IIe Cour civile du Tribunal cantonal du canton du Valais.
Lausanne, le 3 juin 2011
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl Carlin