So I posted up on the Paint.NET message board that I had made a tutorial on gradient creation. After a while, I got a reply from nitebyrd, a user of the forums, in which they explained how they have been making gradients. When I tried it and realized how simple it was to use to make incredible gradients, I asked their permission to make a tutorial out of it so I could share it with you. So, with nitebyrd's permission, here it is!
Please note: This method does not work as advertised in version 2.6. The PDN devs changed the code a bit due to an error when resizing images with a 1px height or width. So, before you scale up the image, you'll have to scale it to 2px wide / high, then up to your desired size. Other than that, it works well. I'd still suggest Rick's revision, though.
It's amazing just how easy this is, so I'm going to get right into it. Open up Paint.NET and create a new image, 1px wide and 2px high. Yes, it's supposed to be that small. Grab your Pencil tool and set your color to whatever you want your first color to be. For this example, I used a random blue color, which ended up being #002AFF. Now zoom in as much as you need to, and use the Pencil on the top pixel of the image. Then change your color to the color you want you gradient to end with and use the pencil to color the bottom pixel of the image. For this example, it ended up being #00D0FF. And it should look like this (zoom level 3200%):

Now when you have your colors, open up the "Resize" dialogue, under Image -> Resize or by pressing [Ctrl]+[R]. Switch the sampling mode to Bilinear. Now, set the height and width to however big you need your final gradient to be. If you need a different aspect ratio than 1-2, make sure you have the "Maintain Aspect Ratio" checkbox unchecked.

When your values are set to your satisfaction, click "OK" and watch the magic! This example went from 1px by 2px to 200px by 100px:

See how easy that was!? Three short paragraphs and we have a gradient! And the beauty of this technique is that it's so versatile. If you want a five-stage gradient, just make your original image 1px wide and 5px high, fill each of the five pixels with the colors you want the gradient to go through, and scale it to whatever final size you need! For examples (5-pixel images zoomed to 3200%, gradient images at 100%):

And that's another way to make a gradient! Again, many thanks to nitebyrd for both sharing this technique with us and allowing me to make a tutorial out of it. As always, if you have questions, about this tutorial or anything Paint.NET, hop on over to the Paint.NET forum and ask away!