そこでapt-file searchですよ

makeinfoってなんだ？ - にたまごほうれん草
makeinfoがない - higepon blog

aptパッケージシステムにおいて、ファイルがどこのパッケージに入っているかを知るにはapt-file searchを使う。

準備

$ sudo apt-get install apt-file
$ sudo apt-file update

使用例

$ apt-file search bin/makeinfo
texinfo: usr/bin/makeinfo

apt-saryを使ってapt-sary-file searchでもよい。

追記

おおお、出ましたよ！でもなんで同じ出力が３つ？？？

推測だけど /etc/apt/sources.list にstable、testing、unstableのエントリが入ってるからかな？