The film of
The End of the Line will be interesting: Charles Clover's book of the same title, which came out a few years ago, is also well worth a read.
It's pretty much as simple as this. That said, it's also a matter of being better informed about what fish on offer is being sustainably caught and what isn't. But it's a complicated subject, the situation changes quite fast and there's a lot of misinformation and greenwash about.
Re. means of cutting overfishing, there's no silver bullet and no one measure that works alone. Quota systems are all very well, but getting the quotas right in the first place is extremely difficult since fish stock modelling is a fairly inexact science, and even if the quotas are okay then they need to be enforced. And they need to be used intelligently in conjunction with other tools such as restrictions on inputs - days at sea, size and type of gear and so on. It's immensely complicated. Some pretty good fisheries management regimes do exist, but they're in the minority.
In Europe, the Common Fisheries Policy has been pretty much a complete failure. It's up for reform in 2012, but that's unlikely to solve all of its problems. Some of the policy tools it uses are okay (although the quota regime is rubbish: it doesn't allow landings of bycatch, which is why a lot is thrown back), but it's got too many players and too many vested interests in keeping the status quo.
The other scandal is that, with European fish stocks in a state, European countries (and others) have been buying access to the territorial waters of poorer nations, especially west African states. Management regimes are usually non-existent or slackly enforced, and high-tech vessels are pretty much free to do immense damage to the fish stocks and often to the local artisan fisheries.
Also, over the last fifty years it's become possible to fish off the continental shelf, exploiting very deep-sea species that weren't targeted before. Very little is known about a lot of these, and what effect the fishing is having on them. Even if it could be established that stocks are becoming depleted, however, it's hard to manage the fishing because it takes place on the high seas, not in anyone's territorial waters.
I read in a UN FAO report a few years ago that there are few known commercial fish stocks that aren't being exploited at or above sustainable levels, and that's not changed and IMHO nor is it likely to soon, although there have been some successes. It's a very worrying situation...