最近の状況。
・FUELが廃止される予定
[url=https://dev.mozilla.jp/2015/06/firefox-40-addon-compatibility/]https://dev.mozilla.jp/2015/06/firefox-40-addon-compatibility/[/url]

・ObserverServiceの通知もいつまででもは使えない予定
[url=https://developer.mozilla.org/en-US/docs/Observer_Notifications#Extension_Manager]https://developer.mozilla.org/en-US/docs/Observer_Notifications#Extension_Manager[/url]


最新の対応方法
・アドオンマネージャを使え
[url=https://developer.mozilla.org/en-US/Add-ons/Add-on_Manager/AddonManager#addAddonListener()]https://developer.mozilla.org/en-US/Add-ons/Add-on_Manager/AddonManager#addAddonListener()[/url]
・サンプル
[url=https://developer.mozilla.org/en-US/Add-ons/Add-on_Manager/Code_Samples#Listening_for_addon_uninstall]https://developer.mozilla.org/en-US/Add-ons/Add-on_Manager/Code_Samples#Listening_for_addon_uninstall[/url]

だそうです。

拙作 Hütte Nippon は対応しました。
[url=https://github.com/mitsugu/JWeather/blob/master/chrome/content/weatheroverlay.js]https://github.com/mitsugu/JWeather/blob/master/chrome/content/weatheroverlay.js[/url]

複数の方法があるのですね。
FUELの方が監視するタイミングが一箇所なので、ソースが少なく簡単
そうですね。

開発中、削除したあと再度追加すると前の設定が残っていたのが気持ち悪かったので
ありがたいです。

お二方、お返事ありがとうございました！

　従来型の拡張であれば[s]FUELを利用すると、[/s] ( FUEL は廃止予定です - 2015/06/20 追記 ) アドオンマネージャを使うことで拡張削除時の処理を簡単に実装できます。サンプルコードを以下に置いています。
[url=https://dev.mozilla.jp/2010/03/processing-uninstall-extension/]拡張アンインストール時になんらかの処理を行う « Mozilla Developer Street (modest)[/url]

Jetpack SDKもといAdd-on SDKでは、アンインストールされた時に行う処理を定義できるようです。
SDKを使わない従来の形式のアドオンの場合、ObserverServiceの通知を使うといいでしょう。
http://www.xuldev.org/blog/?p=68

ちなみにLinuxのパッケージシステムのaptだと、パッケージのアンインストールの方法として、インストールされたファイルを削除する「remove」と、保存された設定等も含めた完全削除の「purge」という2段階の選択肢があります。ですので、上記の方法を使う場合でも、ユーザ設定も含めて削除するかどうかはユーザが選択できるようになっていた方がいいのではないかと思います。

アドオンが削除された際の処理というのは実装する必要はあるのでしょうか？

例えば独自変数を使用した場合、アドオンを削除しても変数は残っていて、
同じアドオンをインストールすると前の設定が反映されてしまいます。
こういった独自に追加した変数を削除したりしなくてよいのでしょうか？

個人的にはこういったものは削除した際に元に戻したいので、必要あるなしに
関わらず方法があれば教えていただきたいです。