I was thinking "apt-show-versions", which is a separate package.

"apt-cache" comes in the "apt" package, and should be installed already. Sorry for the confusion.