The reason I keep coming back to Fisheries is that many of the cases where a permit is required it's because there could be a change to fish habitat—and similarly with navigable waters. So Fisheries and Transport are two of the departments that are the responsible authorities in many cases.
On October 20th, 2011. See this statement in context.