As noted you need a C compiler (see the Modules section of Tutorials for details). However crazyinsomniac maintains another ppm repository that has lots of goodies in it. You can find it a http://crazyinsomniac.perlmonk.org/perl/ppm/ He has Storable so just do:

# for 5.6
ppm install http://crazyinsomniac.perlmonk.org/perl/ppm/Storable.ppd

# for 5.8
ppm install http://crazyinsomniac.perlmonk.org/perl/ppm/5.8/Storable.p
+pd
[download]

Once you have it installed send him a thank you /msg !