I think Instapaper gets a lot of word of mouth spreading because it's an iPhone App. That encompasses a lot more than it sounds. Being an iWhatever App means you get eyeballs from the store, but more importantly from its users - both online and in real life. iPhone/Pad/etc applications are highly sociable and shareable; revealing a useful App to somebody is a form of social value. It's a platform that is in vogue right now: How many times have you been recommended a certain App, or have seen somebody using an interesting one? Ok, now how many times have you been recommended a bookmarklet?
You were blogged a few times, that should have helped somewhat. It's possible that Historious isn't as useful as you think it is. I had written in this box a big long paragraph about why I think that is, but it's not pertinent to your question about promotion. If you'd like more of my thoughts on Historious, shoot me an e-mail, I'd be glad to give you my $.02.
There was also a post around here that detailed a template and methodology for 'pitching' an article about your product to bloggers. The gist of it was: You need to be actively seeking bloggers and promoters, you need to show them you're interested in their work, and you need to pitch them your product in a way that makes them feel their readers will click to read about it.