How to save addon preferences?
I believe you may have a deactivated auto-save option.



In the Blender Preferences bottom left side you have the options, opening these you should see that yours are not hooked on the "Auto-Save Preferences". Hook that option and click "Save Preferences" or make some changes afterwards to trigger the auto-save function.

Should this not be the solution, and it's add-on specific, then i believe that the add-on might not be able to save it's preferences when it get's deactivated.
This could be depending on the code of the add-on, or if that is the case with all add-ons be Blender code related.
In any case, could you please add some examples as to allow trying to replicate the problem.