@Carly and @jballou are correct: a vector illustration is better in this case. Vector based programs allow you to resize the art you make to any size – really infinitesimally small or larger than the state of Texas. It’s really handy to be able to do that in case you want to put your logo on the web or have it be visible from space. The point I’m getting at is that vector art is just more flexible, and all professional graphic designers use it.
When it comes to putting your vector art on the web or using it in print, vector designs can be easily rasterized (turned into one-size-only pixel data) and exported in any of the popular formats, including .jpg, .gif, .png, and .tif.
You mentioned that you felt as though you didn’t have a key piece of information and I think you’re right. Firstly, you mentioned your resolution was 96 pixels per inch. The standard resolution for the web is 72 pixels per inch, and the standard for print media is 300 or higher. When working in a vector-based program, you don’t have to worry about resolution at all. In your case, working with a raster program, you’ll probably want to set your resolution to at least 300 pixels per inch (assuming you’ll want to print it sometime).
The second key piece of information you might need to know is related to an effect called anti-aliasing, which smooths out curves and gets rid of those jaggies you mentioned. I’m not sure about Paint.NET, but most raster and vector programs have anti-aliasing built in and should do it for you automatically.
Finally, there are a few basic things I’ve identified that make web designer logos look so good. 1) They (tastefully) use gradients. 2) They keep it simple. 3) They choose appropriate colors, three at the most. 4) They usually use rounded corners 5) They leverage their site’s shtick (if it’s a site about peanut butter, the logo will have a peanut in it)