How to install the algorithms package?

sudo apt-get install texlive does not install all packages from CTAN. sudo apt-get install texlive-full does that (well, it installs everything that was on CTAN when the package was created).

If you do not want to install everything, you can just install texlive-science which contains the various algorithm-related packages.

On Arch the equivalent meta package is texlive-most.

As mentioned before, texlive doesn't install the entire TeX Live distribution. To install everything, you should use texlive-full, but it contains many packages that you will not even dream of using in the real life.

If you are using Debian/Ubuntu and want to use algorithm + algorithmic, then I would suggest that you simply install texlive-science and go on with life.

If on the other hand, you are feeling adventurous (not really), you may want to check the new version that I have been baking for some time on github, but have still not uploaded to CTAN.

The new version features a slightly easier, streamlined installation procedure, with you having to worry about just one file, algorithms.dtx.

As the original question was about Debian/Ubuntu, I would like to point out a very valuable resource that many may not know, which is the Debian/Ubuntu-specific information on TeX Live. There you will see directives on how to maintain your local packages from stepping onto the distributed versions of those packages, to ease the maintainance task, detailed in Chapter 4.

For those who use tlmgr and were sent here because of modern search engine's tolerance for typos @drozzy's answer got me on the right path:

tlmgr install algorithms

did it. Trying this for algorithm or algorithmic individually didn't work.