A few words on "what is makeinfo" -- other answers cover "how do I get it" well.
The section "Creating an Info File" of the Texinfo manual states that
makeinfo
is a program that converts a Texinfo file into an Info file, HTML file, or plain text.
The Texinfo home page explains that Texinfo itself "is the official documentation format of the GNU project" and that it "uses a single source file to produce output in a number of formats, both online and printed (dvi, html, info, pdf, xml, etc.)".
To sum up: Texinfo is a documentation source file format and makeinfo
is the program that turns source files in Texinfo format into the desired output.