This is actually more of a "How I did it" post, sorry if it's in the wrong forum.
Info wouldn't work in Emacs (version 21.2). I searched the Web up and down to find an answer to this question, but most of the problems people had was with non-existent "dir" files. However, I could see "dir" and all the associated info files sitting in /usr/share/info/.
I looked at the variable "Info-default-directory-list", it was set to about a dozen directories, including /usr/share/info/, but still info wouldn't load.
The problem lay in the variable "Info-directory-list", which for some reason was set to "/usr/share/emacs/packages/gnus", which doesn't even exist on my system. I tried to set Info-directory-list with (setq Info-directory-list "/usr/share/info/") and (setq Info-directory-list (cons "/usr/share/info")), but neither worked; in fact, I got an error upon initialization. What finally worked was using (setq Info-directory-list nil) so that the directories from Info-default-directory-list would be used instead.
I also had to use (setq Info-default-directory-list (cons "/usr/share/info/xemacs" Info-default-directory-list)) so that my info files from Xemacs could be used as well.
Now info doesn't work under Xemacs (it did before), but I don't really care, I'm happy using GNU-Emacs.