The hstore extension creates functions that call code from an external dynamic object, which requires superuser privilege. That's why creating the hstore extension requires superuser privilege.
As for Heroku, it is my understanding that they are running with a special extension whitelisting module, which allows users to create certain extensions even though they are not superusers. I believe it is based on this code: https://github.com/dimitri/pgextwlist. You can try to install that code yourself if you want the same functionality in your databases.