Sachverhalt: A. Die Misoxer Kraftwerke AG (MKW) nutzt gestützt auf rechtsgültige Wasserrechtsverleihungen die Wasserkraft der Flüsse Calancasca und Moesa sowie deren Zuflüsse (insbesondere des Ri de Buffalora) im oberen Misox zur Erzeugung elektrischer Energie. Dazu betreibt sie insgesamt zehn Wasserentnahmen. Die bestehenden Konzessionsverhältnisse enden in den Jahren 2041 bis 2043. Am 17. Mai 1992 hat das Schweizer Stimmvolk der Revision des Bundesgesetzes über den Schutz der Gewässer (GSchG; SR 814.20) zugestimmt. Der Bundesrat hat diese auf den 1. November 1992 in Kraft gesetzt. Neue Wasserentnahmen aus einem Fliessgewässer sind seit dem lnkrafttreten des revidierten Gesetzes nur noch unter den Voraussetzungen von Art. 29 ff. GSchG möglich, sie bedürfen einer entsprechenden Bewilligung. Für bestehende Wasserentnahmen trifft das GSchG eine Übergangsregelung und verlangt, dass diese bis zum 31. Dezember 2012 saniert werden (Art. 81 Abs. 2 GSchG). Am 16. Februar 1993 hat die Regierung des Kantons Graubünden das Sanierungsverfahren für die Restwassermengen der Wasserläufe des Kantons in die Wege geleitet. Betreffend die zehn Wasserentnahmen der MKW hat das Amt für Natur und Umwelt des Kantons Graubünden (ANU) zwei Berichte verfasst, den Bericht zur Sanierung von Gewässern i.S.v. Art. 80 Abs. 1 GSchG vom 24. März 2003, überarbeitet am 7. Mai und am 3. August 2009, und den Bericht zur Sanierung von Gewässern i.S.v. Art. 80 Abs. 2 GSchG vom 6. August 2009. Auf der Grundlage dieser beiden Berichte des ANU fasste die Regierung an ihrer Sitzung vom 24. November 2009 den folgenden Beschluss: "1. (a) Die Misoxer Kraftwerke AG wird gestützt auf Art. 80 Abs. 1 GSchG verpflichtet, bei der Wasserentnahmestelle in Curina bis spätestens Ende 2012 eine Dotiereinrichtung zu erstellen und ab diesem Zeitpunkt Dotierwassermengen im Umfang einer Jahreswasserfracht von 4,734 Mio. m3 nach folgender Regelung abzugeben: Oktober und November: 230 bis 350 l/s, Mittel 290 I/s Dezember bis März: 200 I/s April bis September: 0 bis 150 l/s, Mittel 70,5 l/s (b) Zudem hat die Misoxer Kraftwerke AG die Erhebungen in der Flusssohle zwischen der Fassung Curina und dem Grundwasseraufstoss Andrana maschinell abzutragen. (c) Die Misoxer Kraftwerke AG wird verpflichtet, nach Angaben des Amtes für Natur und Umwelt und des Amtes für Jagd und Fischerei über einen Zeitraum von 5 Jahren ein Monitoring durchzuführen. Das Ergebnis des Monitorings ist der Regierung in Form eines Berichtes zu unterbreiten. Sofern das Monitoring das Erfordernis einer Umverteilung der Dotierwasserabgaben nachweist, stellen die Fachstellen der Regierung einen entsprechenden Antrag. Der Umfang der Jahreswasserfracht von 4,734 Mio. m3 bleibt dabei unverändert. 2. Die Misoxer Kraftwerke AG wird bezüglich ihrer Wasserentnahmen von einer Sanierungspflicht nach Art. 80 Abs. 2 GSchG befreit. (...)." Diesen Beschluss fochten Pro Natura, der WWF und der SFV mit Beschwerde vom 11. Januar 2010 beim Verwaltungsgericht des Kantons Graubünden an, welches die Beschwerde mit Urteil vom 12. November 2010 abwies. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht vom 31. Mai 2011 beantragen Pro Natura, der WWF und der SFV, das Urteil des Verwaltungsgerichts vom 12. November 2010 sei aufzuheben, und die Sache sei zu neuer Entscheidung an die Vorinstanz oder an die Regierung zurückzuweisen. Die Vorinstanz beantragt, die Beschwerde sei abzuweisen, soweit auf diese einzutreten sei. Die Regierung und die MKW stellen Antrag auf Beschwerdeabweisung. Das Bundesamt für Energie BFE verzichtet auf eine Vernehmlassung. Das Bundesamt für Umwelt BAFU hat eine Stellungnahme zur Beschwerde eingereicht, ohne ausdrücklich Anträge zu stellen. Die betroffenen Gemeinden haben sich nicht geäussert. Im Rahmen des zweiten Schriftenwechsels halten die Verfahrensbeteiligten an ihren Standpunkten fest.