I know this is an older post, but maybe I can contribute.
The size I used in both Photoshop & Gimp are below. I created a new "page" using those settings. You can
use whatever graphics program you like. I don't know of a program with templates for MD labeling.
Size: Minidisc shell label space = 3.6 cm x 5.3 (448 pixels x 637 pixels) @ 72 dpi (Sony style disc label area)
Size: Label slip case = 7.2 cm x 5.3 cm (862 pixels x 650 pixels) @ 300 dpi
The paper I use is Avery sticker paper (#3383) or you can use a full size (A4/US letter) shipping label. I run
it through an inkjet printer. They always turn out well.
Also, be sure to save the label so you can use it again as a template if you like. Photoshop/Gimp are great for
this as you can save it with the layers and just replace the album artwork on the layer.