Update:
I just realized one can figure from your question you are targeting Office versions up to and including 2003 right now, as for example the tools menu is gone in 2007.
You might still find an answer regarding your question by looking at the starting point for the mentioned migration from 2003 to 2007: access to the settings for the sample 2003 add-in is located in an add-in specific sub menu of the tools menu, as shown in Figure 7.
For current and future versions of Office (i.e. 2007 and up) your first stop regarding user interface questions should be the Office Fluent User Interface Developer Portal, specifically you'll find there the '2007 Office System Document: UI Style Guide for Solutions and Add Ins'.
Its probably worth pointing out that this guide is not on par with the Windows User Experience Interaction Guidelines (UX Guide) by a huge margin, which is unfortunate given the almost traditional friendly competition between the Office team and other Microsoft depatments in setting the next de facto UI standard for 3rd party developers.
Still one can figure out initial directions from there, for example the recommendation regarding scenarios for custom task panes as suggested by Gary clearly is at odds with your need to offer user settings, citation:
Create a custom task pane if…
Your solution needs to present data
about a document that is required to
be visible, in a non-modal fashion,
use a custom task pane. [...]
You can find a good starting point regarding your question in section Simple Migration, where the migration of a simple 2003 add-in to the current 2007 release is explored step by step from a UI design perspecive; not surprisingly this add-in features settings too, hence your requirements are addressed, albeit only on the side.
Reproducing this section here would be a bit lengthy plus I'm not sure whether it would be legal to reproduce the inline images used there, just look for Figure 9 in particular to get you started.
You can take it further from there depending on your particular scenario, good luck!