Get some pens specifically designed for drawing and handwriting, and trace pencilled outlines with the pen. Where connecting surfaces can be seen, do a thin outline, where they can't be seen, do a thicker one (so edge lines will be darker, giving a bolder image).
Erase the pencilled lines, at least enough that the scanner won't pick them up, or that they can be easily culled using a 'levels' feature. Scan at 300dpi and save as a black and white PNG file.
Download Inkscape for free. Import the PNG lineart into Inkscape. Select the image, go to properties, and check the 'fit to selection' button. It should resize the document to the size of your lineart.
With the lineart selected, look for the 'Trace Bitmap' function in the 'Path' menu. Leave the settings as they are and click OK. This should generate a vectorised version of your lineart. Delete the image underneath it to see the lines more clearly.
If it's too thick, or too faint, undo the delete and erase the vector version instead. Reselect the bitmap and try again, altering some of the settings (specifically, the Brightness Threshold). Keep trying it till you get a result you're happy with.
Save in plain SVG format. Import into the raster graphics app of your choice (PSP, Photoshop, GIMP, whatever). Note that you can scale it up even bigger now that it's a vector image. Store it as a layer and paint under it.
Then shrink down to the size you want and save it. Voila! Super-smooth lineart!