GMail uses a old draft version of the API, and they check for the vendor-specific window.webkitNotification rather than the spec window.Notification, so a Firefox add-on or a GMail update is necessary.
I recommend the Firefox Aurora channel. It's a nice balance between bleeding edge and beta. That said, I've used Firefox Nightly for years and I've found bugs, as expected, but nothing critical.
One caveat is that some people are annoyed by the daily update notifications. If you set the about:config pref "app.update.silent" to true, Firefox should never show you an update dialog:
You have to authorize every domain that wants to use the notifications. Besides that, it has to be a user action, the authorization. You can't automate this process without some hacking.
Love the notification API for my webapps. Wish there was a sign of IE adopting this technique so i can implement this mainstream.
Now if only Outlook Web App used this style of notifications instead of an in-page popup, it would finally be simple to ditch Outlook in companies that still use Exchange.
http://jbalogh.me/2012/01/30/push-notifications/
These would have allowed sites to send you notifications after you had left the page, like iOS's push notifications work.