I just noticed that someone has created official Debian packages for Osmium (libosmium-dev, osmjs). They have also found their way into the new Ubuntu 12.04 version. Unfortunately they are already outdated. It is fine if you only want to use osmjs, but if you do any development based on Osmium, I suggest you use the version from github.
Osmium pretty much is still a moving target. I’d like to release proper versions and have a stable version other can build upon, but that means more work and I don’t have that extra time at the moment.
[Updated on 2012-07-15: Include link to osmjs package]