Starting with version 3.0, Paint.NET allows the creation of custom palette files. The default palette looks like this:
It's not bad, but I found it a little disorganized for my taste. Luckily, you can create your own custom palette files.
In case you were wondering, I thought I would show you my custom palette.
If you would like to add my custom palette to your list of available palettes, simply right click on the following link and pick "Save target as..." from the menu. Save the file in your My Documents\Paint.NET User Files\Palettes directory.
You can open the Palettes folder by clicking on the icon in the color docker:
This will open a window where all of your palette files are stored. Just put the custom palette file into that directory and you should be all set.
For more information about Paint.net and custom palettes, see this page.