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. 