Wasserrechtskonzession, Abschreibungsverfügung, hat sich ergeben:
A.- Die Kraftwerk Birsfelden AG ersuchte Ende 1995 um eine Erweiterung der Konzession für die Nutzung der Wasserkraft des Rheins bei Birsfelden. Sie beabsichtigte, durch eine Absenkung der Rheinsohle unterhalb des Kraftwerks das nutzbare Gefälle zu erhöhen und so eine Mehrnutzung zu erzielen.
Das Eidgenössische Departement für Umwelt, Verkehr, Energie und Kommunikation erteilte die nachgesuchte Konzessionserweiterung am 14. Juli 1998.
B.- Gegen diesen Entscheid erhoben verschiedene Fischereiverbände und Umweltorganisationen gemeinsam Verwaltungsbeschwerde bei der Eidgenössischen Rekurskommission für die Wasserwirtschaft. In der Folge traten die Beschwerdeführenden und die Kraftwerk Birsfelden AG in Vergleichsverhandlungen. Diese führten zu keinem von allen Beteiligten angenommenen Ergebnis. Am 13. Oktober 1999 erklärte die Kraftwerk Birsfelden AG, sie verzichte auf das Erweiterungsprojekt, und zog ihr Gesuch um Erteilung einer Zusatzkonzession zurück. Daraufhin schrieb die Rekurskommission das Verfahren am 12. November 1999 als gegenstandslos ab. Sie erhob keine Verfahrenskosten und sprach keine Parteientschädigungen zu.
C.- Der kantonale Fischerei-Verband Basel-Land, der Fischereiverein Baselland und Umgebung, der Fischereiverein Birsfelden sowie der Landesfischereiverband Baden e.V. haben gegen die Abschreibungsverfügung der eidgenössische Rekurskommission für die Wasserwirtschaft, das Fernmelde- und Postwesen am 13. Dezember 1999 beim Bundesgericht Verwaltungsgerichtsbeschwerde und Rechtsverweigerungsbeschwerde erhoben. Sie beantragen die Aufhebung des angefochtenen Entscheids, soweit die Rekurskommission das Verfahren als gegenstandslos abgeschrieben und ihnen keine Parteientschädigung zugesprochen hat, sowie die Rückweisung der Sache an die Vorinstanz zu neuem Entscheid im Sinne ihrer Ausführungen. In diesen rügen die Beschwerdeführenden im Wesentlichen, dass die Rekurskommission darauf verzichtet hat, die zuständigen Konzessionsbehörden zur Anordnung fischereirechtlicher Sanierungsmassnahmen zu verpflichten.
D.-Das Eidgenössische Departement für Umwelt, Verkehr, Energie und Kommunikation sowie die Kraftwerk Birsfelden AG beantragen die Abweisung der Beschwerde. Die Rekurskommission des Eidgenössischen Departements für Umwelt, Verkehr, Energie und Kommunikation, welche die eidgenössische Rekurskommission für die Wasserwirtschaft, das Fernmelde- und Postwesen per 1. Januar 2000 abgelöst hat (vgl. AS 1999 3497), erklärte Verzicht auf Vernehmlassung.

Das Bundesgericht zieht in Erwägung:
1.- a) Die Verwaltungsgerichtsbeschwerde ist zulässig gegen Verfügungen, die sich auf öffentliches Recht des Bundes stützen oder hätten stützen sollen (Art. 97 OG in Verbindung mit Art. 5 VwVG), sofern diese von einer in Art. 98 OG genannten Vorinstanz erlassen worden sind und keiner der in Art. 99 ff. OG oder in der Spezialgesetzgebung vorgesehenen Ausschlussgründe greift. Soweit die Verwaltungsgerichtsbeschwerde zulässig ist, kann der Beschwerdeführende auch geltend machen, der angefochtene Entscheid verletze Bundesverfassungsrecht, weil dieses zum Bundesrecht im Sinne von Art. 104 lit. a OG gehört (<ref-ruling> E. 2d/bb S. 47 mit Hinweisen).
Die Beschwerdeführenden rügen, die Vorinstanz habe zu Unrecht darauf verzichtet, den Erlass einer Sanierungsverfügung vorzuschreiben, und es sei ihnen zu Unrecht keine Parteientschädigung zugesprochen worden. Das vorinstanzliche Verfahren war vollständig vom Bundesrecht, in materieller Hinsicht namentlich durch das Bundesgesetz vom 21. Juni 1991 über die Fischerei (BGF, SR 923. 0) und hinsichtlich des Verfahrens durch das Bundesgesetz vom 20. Dezember 1968 über das Verwaltungsverfahren (VwVG, SR 172. 021) beherrscht, so dass alle Rügen der Beschwerdeführenden im Verfahren der Verwaltungsgerichtsbeschwerde behandelt werden können.
b) Der Fischereiverein Baselland und Umgebung und der Fischereiverein Birsfelden sind gemäss den unbestrittenen Angaben in der Beschwerdeschrift gemeinsam Pächter der basellandschaftlichen Rhein- und Birsstrecken, die im Konzessionsabschnitt der Beschwerdegegnerin oder in deren unmittelbarer Nachbarschaft liegen. Als Pächter wurden sie vom ursprünglich angefochtenen Konzessionsentscheid unmittelbar in schutzwürdigen eigenen Interessen betroffen. Der angefochtene Entscheid berührt ihre Interessen insofern, als er eine Änderung der bestehenden Konzession stillschweigend ablehnt und den Beschwerdeführenden überdies eine Parteientschädigung versagt. Ihre Legitimation gemäss Art. 103 lit. a OG ist daher zu bejahen. Die beiden Fischereivereine haben ihr Rechtsmittel gemeinsam mit dem kantonalen Fischerei- Verband Basel-Land und dem Landesfischereiverband Baden e.V. eingereicht. Da auf die Beschwerde der beiden Fischereivereine ohnehin einzutreten ist, kann die Legitimation der beiden anderen beschwerdeführenden Verbände aus prozessökonomischen
Gründen dahingestellt bleiben.
2.- Die Beschwerdeführenden hatten der Rekurskommission für den Fall, dass die Beschwerdegegnerin das Konzessionsgesuch zurückziehen sollte, beantragt, die zuständigen Konzessionsbehörden seien anzuweisen, die im Hauptantrag beantragten Massnahmen im Rahmen eines fischereirechtlichen Sanierungsverfahrens anzuordnen. Die angefochtene Abschreibungsverfügung äussert sich nicht zu diesem Antrag. Die Beschwerdeführenden erblicken darin eine formelle Gehörsverweigerung.
a) Eine formelle Rechtsverweigerung und damit eine Verletzung von Art. 4 aBV bzw. Art. 29 Abs. 1 BV liegt nach der bundesgerichtlichen Rechtsprechung unter anderem dann vor, wenn eine Gerichts- oder Verwaltungsbehörde ein Gesuch, dessen Erledigung in ihre Kompetenz fällt, nicht an die Hand nimmt und behandelt (<ref-ruling> E. 3b S. 164). Eine Behörde muss ein ihr unterbreitetes Gesuch materiell nur behandeln, wenn und soweit sie dafür zuständig ist. Soweit sich eine Behörde für unzuständig hält, hat sie einen Nichteintretensentscheid zu fällen, sofern ihre Unzuständigkeit nicht derart offen zu Tage tritt, dass sie von jedermann, auch vom rechtsuchenden Laien, erkannt werden kann (Urteil des Bundesgerichts vom 19. Dezember 1979, ZBl 81/1980 S. 265 ff. E. 2c).
b) Die Vorinstanz hat den Eventualantrag der Beschwerdeführenden mit Stillschweigen übergangen. Es liesse sich fragen, ob dieses Verhalten nicht insofern gerechtfertigt war, als die Rekurskommission für die Behandlung des Eventualantrages offensichtlich unzuständig war (vgl. die nachfolgende Erwägung 3). Diese Frage kann offen bleiben. Eine formelle Rechtsverweigerung liegt jedenfalls deshalb nicht vor, weil die Vorinstanz nicht einfach untätig geblieben ist, sondern durch ihre Abschreibungsverfügung zumindest sinngemäss zum Ausdruck gebracht hat, dass sie auf den Eventualantrag der Beschwerdeführenden nicht eintritt.
c) Problematisch ist hingegen, dass sie das Nichteintreten nicht begründet hat. Der Anspruch auf rechtliches Gehör umfasst unter anderem auch den Anspruch auf eine hinreichende Begründung des angefochtenen Entscheides. Zwar verletzt eine urteilende Instanz den Anspruch auf rechtliches Gehör bzw. die daraus folgende Begründungspflicht nicht bereits dadurch, dass sie sich nicht mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Sie kann sich vielmehr auf die für den Entscheid wesentlichen Punkte beschränken. Es genügt, wenn sich der Betroffene über die Tragweite des Entscheides Rechenschaft ablegen und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann (<ref-ruling> E. 4 S. 86, mit Hinweisen). Vorliegend hätte die Rekurskommission zumindest kurz darlegen müssen, weshalb sie auf den Eventualantrag nicht eingetreten ist. Insofern liegt eine formelle Rechtsverweigerung vor. Es ist nicht auszuschliessen, dass ein hinreichend motivierter Beschluss den unnötigen Rechtsgang vor Bundesgericht vermieden hätte.
d) Für den Fall, dass das Bundesgericht eine formelle Rechtsverweigerung bejaht, ersuchen die Beschwerdeführenden das Bundesgericht, die Angelegenheit nicht schon aus diesem Grund an die Vorinstanz zurückzuweisen, sondern selbst zu entscheiden. Dieses Vorgehen erweist sich hier ohne weiteres als sachgerecht, da der Mangel der Gehörsverweigerung in einem Fall wie dem vorliegenden durch das Verfahren vor Bundesgericht geheilt werden kann (vgl. <ref-ruling> E. 2 S. 72 mit Hinweisen).
3.- a) Im Verfahren der Beschwerde an eine eidgenössische Rekurskommission und im Verfahren der Verwaltungsgerichtsbeschwerde an das Bundesgericht bildet die ursprüngliche Verfügung als Anfechtungsobjekt den Ausgangspunkt des Verfahrens und zugleich den Rahmen und die Begrenzung des Streitgegenstandes (<ref-ruling> E. 1d S. 417 mit Hinweis). Gegenstand des Beschwerdeverfahrens kann nur sein, was Gegenstand des erstinstanzlichen Verfahrens war oder nach richtiger Gesetzesauslegung hätte sein sollen (André Moser/Peter Uebersax, Prozessieren vor eidgenössischen Rekurskommissionen: die erstinstanzliche nachträgliche Verwaltungsgerichtsbarkeit im Bund, Basel/Frankfurt a.M. 1998, Rz 5.8). Gegenstände, über welche die erstinstanzlich verfügende Behörde nicht entschieden hat und über welche sie auch nicht entscheiden musste, dürfen die Rechtsmittelinstanzen nicht beurteilen, weil sie dadurch die funktionelle Zuständigkeit der ersten Instanz missachten würden (Alfred Kölz/Isabelle Häner, Verwaltungsverfahren und Verwaltungsrechtspflege des Bundes, 2. Auflage, Zürich 1998, Rz. 404). Vorliegend war ausschliesslicher Gegenstand der ursprünglichen Verfügung die Zusatzkonzession für die Nutzung des Rheins nach einer Tieferlegung der Rheinsohle. Hingegen befasste sich diese Verfügung nicht mit der Frage, ob und in welchem Umfang allenfalls Sanierungsmassnahmen unabhängig von einer Konzessionsänderung anzuordnen seien. Daher fehlt es in diesem Punkt an einer Verfügung nach Art. 5 VwVG, welche Gegenstand eines Rechtsmittelverfahrens sein konnte (vgl. <ref-ruling> E. 5b S. 118). Die Rekurskommission ist daher zu Recht auf das entsprechende Begehren der Beschwerdeführenden nicht eingetreten.
b) Nichteintreten war auch aus einem weiteren Grund geboten. Nachdem weder konkrete Sanierungsmassnahmen Gegenstand der erstinstanzlichen Verfügung bildeten noch auch nur die Frage, ob solche Massnahmen geboten seien, hätte deren Anordnung durch eine übergeordnete Instanz aufsichtsrechtlichen Charakter gehabt. Aufsichtsrechtliches Einschreiten setzt neben anderem eine Aufsichtskompetenz voraus, die aus der übergeordneten Stellung in der Diensthierarchie folgt. Verwaltungsunabhängige Rechtsmittelbehörden besitzen eine entsprechende Kompetenz nur in seltenen Fällen und kraft ausdrücklicher gesetzlicher Regelung (vgl. Fritz Gygi, Bundesverwaltungsrechtspflege, 2. Auflage, Bern 1983, S. 213 mit Hinweisen; Moser/Uebersax, a.a.O., Rz 5.8). Die Zuständigkeit der Rekurskommission für die Wasserwirtschaft (bzw. nachher Rekurskommission für die Wasserwirtschaft, das Fernmelde- und Postwesen und heute Rekurskommission des UVEK) ergibt sich aus Art. 71a Abs. 1 VwVG. Danach beschränkt sich ihre Aufgabe auf die Beurteilung von Beschwerden. Über Aufsichtskompetenzen verfügt sie nicht.
c) Es bedarf bei der geschilderten Rechtslage keiner weiteren Erläuterungen, dass es nicht Sache des Bundesgerichtes sein kann, gewissermassen erstinstanzlich Sanierungsmassnahmen nach Art. 10 BGF anzuordnen.
4.- Die Beschwerdeführenden bemängeln, dass ihnen für das Rekursverfahren keine Parteientschädigung zugesprochen wurde. Sie machen geltend, sie hätten sowohl im Einsprache- als auch im Beschwerdeverfahren erhebliche Umtriebe gehabt; die Beschwerdegegnerin sei aufgrund des Rückzugs des Konzessionsgesuches als materiell unterliegende Partei anzusehen.
Gemäss Art. 64 Abs. 1 VwVG kann die Beschwerdeinstanz der ganz oder teilweise obsiegenden Partei eine Entschädigung für ihr erwachsende notwendige und verhältnismässig hohe Kosten zusprechen.
Die Rekurskommission hat erwogen, die Beschwerdeführenden hätten mit ihrem Rechtsbegehren nicht obsiegt. Es sei ihnen nicht um die Aufhebung der Zusatzkonzession, sondern um die Ergänzung der Umweltschutzauflagen im Sinne ihrer Eingaben gegangen. Mit dieser Erwägung setzen sich die Beschwerdeführenden nicht auseinander. Diese erscheint - übrigens auch im Lichte dessen, was die Beschwerdeführenden vor Bundesgericht verlangen - ohne weiteres als zutreffend. Es ist daher nicht zu beanstanden, dass die Rekurskommission die Beschwerdeführenden nicht als obsiegend im Sinne von Art. 64 Abs. 1 VwVG angesehen und ihnen daher keine Parteientschädigung zugesprochen hat.
5.- Der Vorinstanz ist zwar eine formelle Rechtsverweigerung vorzuwerfen; indessen dringen die Beschwerdeführenden mit keinem ihrer Anträge durch. Sie sind daher als unterliegende Partei anzusehen. Bei diesem Ausgang werden sie kostenpflichtig (Art. 156 Abs. 1 OG). Da es sich um lokal bzw. regional tätige Organisationen handelt, deren Anliegen nur teilweise rein ideeller Natur sind, besteht kein Anlass, sie den gesamtschweizerischen Organisationen, die sich dem Schutz der Umwelt und der Landschaft widmen, gleichzustellen und praxisgemäss (<ref-ruling> E. 10 S. 357) von den Gerichtskosten zu befreien. Zudem haben sie die Beschwerdegegnerin für deren Aufwand im bundesgerichtlichen Verfahren angemessen zu entschädigen (Art. 159 Abs. 2 und 3 OG).

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Die Gerichtsgebühr von Fr. 2'000. -- wird den Beschwerdeführern auferlegt.
3.- Die Beschwerdeführer haben der Beschwerdegegnerin eine Parteientschädigung von Fr. 2'000. -- zu bezahlen.
4.- Dieses Urteil wird den Parteien sowie dem Eidgenössischen Departement für Umwelt, Verkehr, Energie und Kommunikation (UVEK) und der Rekurskommission des Eidgenössischen Departements für Umwelt, Verkehr, Energie und Kommunikation (REKO) schriftlich mitgeteilt.
_
Lausanne, 12. Juli 2000
Im Namen der I. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Das präsidierende Mitglied:
Die Gerichtsschreiberin: