makeinfo is part of the texinfo distribution. Get texinfo-*.tar.gz. However, all GNU distributions should come with prebuilt info files, thus makeinfo should not be needed. If you notice a distribution that does not come with *.info files, please report it as a bug.