In firefox, change the dom.webnotifications.enabled config to false. Type about:config in the address bar, accept the warning, search for the key and toggle it.

In Chrome, Preferences → Advanced → Content Settings → Notifications → [Enable Blocked].

My recommendation: leave. Websites won't stop doing something intrusive and annoying until it costs them more than it gets them.

Unfortunately that hasn't worked for those infuriating "sign up for our email!" popovers/interstitials. Indeed, they seem to work better than ever.

Yeah but how are they going to realize people are leaving because of that one specific thing?

They are doing A/B tests on something like that, right?

There's a sense it which it isn't your responsibility to figure that out. If they never check, you avoid annoyance. If they do check (A/B test, eyeballing it, whatever), they'll see. If they're unwilling to turn it off no matter what then they're kind of terrible, and probably should lose lots of traffic.

Natural selection. Sites that use this tactic would get less revenue and thus have a higher chance of dying than those that don't. Therefore, over time, sites would trend towards not having that feature.

They really should be asking on the second visit. I've enabled them for some sites (actually, this reminds me I haven't seen notifications for one in a while) but popping up before I've had time to assess the content is rude.

The question I often end up asking myself is "what possible reason could this website think I have for wanting notifications from them?", this site being a great example. I guess the sad reality is they want you to just dismiss the popup with the primary button, without thinking, so they can spam you.