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.