Well, if you're planning on doing this with vanilla Perl, you'll definitely want to get the images into a format that's pleasant to work with, which is Targa. (Head on over to http://wotsit.org to get the Targa specs; you'll probably want RGB, non-compressed.) So what you'll want to do is:

1. Get the image into Targa format
2. Strip the header, getting useful information like image dimensions out of it. Use unpack for this, I think.
3. Read the image data.
4. Take the weighted average of MxN pixel blocks, where M is (image_x/thumb_x) and N is (image_y/thumb_y), to get each of the thumbnail pixels. You'll probably have to do a bit of gamma correction to get the colours right, but with small images you might not have to. You can get as tricky as you want with this step, but DON'T just pick a random pixel (or the top-left pixel) in each sample rect, unless you don't mind the thumbnail looking like crap. Read up on supersampling for more info.
5. Write out a smaller Targa with the thumbnail data.

Targas are nice and easy to work with. By the way, I've run across some TGA headers generated by ImageMagick that were missing some (admittedly nonessential) data, so be careful with that.