It does work in FF4, but it's not widely supported enough to rely on just yet, you're right.
I also find the best thing to do is use a hybrid approach (pushState where available, hashbang as a fallback.) If anyone else is interested in implementing this, there are some good frameworks[1][2] to give functionality similar to pushState via the fragment identifier.
Note that these constantly poll the hash in browsers that don't support the onhashchange event. It's a good idea to turn down the polling frequency to half a second or so, because I've found it can cause performance problems in IE.
Push state is really good because it lets the server know what's going on, but it did not work in Firefox when I last checked.