I thought CGI.pm came bundled with Perl.

Yes. I don’t use Fedora, but according to the Fedora Project wiki, Fedora 16 features 100% “Update Perl to 5.14.”, and from perldoc it appears that CGI is a core module in Perl 5.14.0.

How do I know if a particular module is installed on my system?

See the FAQ http://perldoc.perl.org/perlfaq3.html#How-do-I-find-which-modules-are-installed-on-my-system%3f, or this PerlMonks node from 2005: Finding All Installed Modules.

What is best way to install Perl modules?

I find cpanm works fine. See http://www.cpan.org/modules/INSTALL.html, http://search.cpan.org/~miyagawa/App-cpanminus-1.5013/bin/cpanm, and http://bouncehammer.jp/en/email-topics/2011/06/install-perl-modules-using-cpanm-command.html. (But I’m on Windows, and YMMV.)

HTH,