The redfish was a type of fish native to Earth.
When Spock tried to match the sound of the Whale Probe to the sound of an Earth animal aboard the Klingon Bird-of-Prey HMS Bounty, a Sebastes mustinus, a type of redfish, was one of the animals shown. (Star Trek IV: The Voyage Home)
Benjamin Sisko and Jake served redfish in a dinner for the senior staff of Deep Space 9 in 2371. (DS9: "Equilibrium")
In an alternate timeline, Korena served redfish in a dinner between Jake, Nog and herself. She claimed they were "fresh from the bayou". (DS9: "The Visitor")
There are several types of fish commonly called "redfish". The edible kinds are the rockfish (genus Sebastes) and the snappers (family Lutjanidae).
The scientific name for the redfish was shown as Sebastes mustinus, which does not exist, in Star Trek IV. There is a species, on the other hand, with the name Sebastes mystinus. We can assume that the computer on the HMS Bounty was in error.