If your module is going onto CPAN then you should also have POD at the end which documents the class - that is one place where your example script can go, as well as a description of the methods. See perlpod, and any of the modules in the base.

Should the module need use CGI even if the calling script is using it already, does this load it twice?
As a general principle your module should load and compile without assuming the caller has done anything, it should be a "black box". If the caller (or any other modules) duplicate loading modules then that is OK, they are not loaded more than once - just do not assume any particular load order.