What version of perl are you using? Activestate, perl for win 32 or a cygwin port?
If using activestate, look on their site, becouse they have their own version of the perl -MCPAN like command. (i don't know it exactly, since i don't use it, you ought to find it here: http://aspn.activestate.com/ASPN/docs/ActivePerl)
Ah found it, use ppm.