You need to find a nice cheap certificate authority who Microsoft are friendly with - I can't unfortunately remember off the top of my head which ones are, and I went for a relatively expensive one, Thawte - and generate a certificate signing request using some free tools that come with MS dev tools or I think the JDK ones will do it too.
Then you use the MS devkit tools to sign the executable with the certificate that the certificate authority sends back to you. It costs money. You need to be verifiably a company or organisation as well. Otherwise you'll be using a free certificate which still puts up a scary(ish) dialog.