I see that it uses CGI::Utils, but I don't see anywhere in the source that CGI::Cookie uses CGI.pm

I see this as well.
Although CGI::Cookie is intended to be used in conjunction with CGI.pm (and is in fact used by it internally), you can use this module independently.

-Lee

"To be civilized is to deny one's nature."