Mercury is wicked bad for children, babies and fetuses, but as far as we know now not nearly as dangerous to adults. So it’s definitely a concern if you are a child, nursing, or going to be pregnant in the near-to-medium future. If so you should definitely limit or avoid swordfish, tuna (except some canned tuna) or shark, and limit freshwater fish as well. Here’s info from an environmental group: http://www.nrdc.org/health/effects/mercury/walletcard.PDF
For adults who are not going to be pregnant or nursing, current understanding is that mercury levels in fish aren’t of particular concern.
Overfishing is of course a different issue, but there are plenty of resources for what fish are thought to be currently sustainable. Hey, surprise, the same link above also talks about that!