Are they already digital, or are you scanning them?
If scanning small originals, use the highest optical resolution of your scanner.
If already digital, Irfanview -
www.irfanview.com makes a pretty good job of enlargement - the Lanczos interpolation filter is about the best for sharpness.
I believe there is a trial version of "Genuine Fractals", supposedly the most powerful enlargement program.
http://www.lizardtech.com/download/dl_options.php?page=gf
Personally, I reckon it's just fractal hocus pocus, and you could do as well by other methods.
Some people swear by carrying out really big enlargement in several steps.
I would start by applying a sharpen or "unsharp mask" if the original benefits from it - you want the original as good as it can be, before the next step.
You cannot recover detail that just isn't there though, the best any enlargement can achieve is to keep edges there that should be, and stay smooth where it should be - the outer limits of those two being:
1. Pixel magnify, no interpolation (sharp, but ugly)
2. Linear interpolation (soft/blurred)
The best interpolation algorithm has to make a good guess if there is an edge that should be sharp, or a gradient that should be smooth - that's why you MUST sharpen the original if it needs it, to strengthen that clue.
If you want to try some other software, in alt.comp.freeware (newsgroup) they have been raving about Photofiltre
http://photofiltre.free.fr/
There IS an English version - and remember, Telechargements = Downloads