昨日辺りから急にcookieが保存されなくなってしまったようなのです。
例えば、http://www.google.co.jp/の「表示設定」で「検索言語」の設定を
「優先する言語：日本語」に設定して「保存」すると、
次回新たにgoogleを開いた時に「日本語のページを検索」にチェックが入っているのですが、
Firefoxを再起動してしまうと、ウェブ全体から検索にチェックが戻ってしまいます。
その他のサイトでも、Firefoxを再起動するとログイン情報等が初期化されてしまうようで、
Firefoxを再起動する度に毎回ログインしなおさなければいけない等、
cookieが保存されなくなってしまったもしくは
Firefox再起動でcookieが初期化されてしまうようなのです。
今まではそのようなことはありませんでした。

「ツール」の「オプション」の「プライバシー」の「Cookie]の設定は、
「サイトから送られてきたCookieを保存する」
「サードパーティのCookieも保存する」
両方にチェックを入れていて
「Cookieを保存する期間：サイトが指定した期間まで」と設定しています。
「例外サイト」には何も登録されていません。
また、「プライバシー情報」の設定は、
「Firefoxの終了時にプライバシー情報を消去する」
はチェック無しで、
「プライバシー情報を消去する前に確認する」
にチェック有りです。
Firefoxはバージョン3、OSはWinXPを使用しています。
使用しているアドオンは、FireGestures1.1.2と、TabMixPlus0.3.6.1.080416です。

どなたか解決法をご教授願えませんでしょうか。
よろしくお願い致します。

Cookie ファイルが損傷したのでしょうかね？
試していただきたいことは
・プライバシー情報か Cookie を表示... からCookie を削除して Firefox を再起動する
・Cookie とキャッシュを削除してから Firefox を再起動して、問題のサイトで設定を保存する
・ユーザプロファイルフォルダから cookies.sqlite をデスクトップに退避してから Firefox を起動して、問題のサイトで設定を保存する
解消しないようなら
・セーフモードで起動するとどうなるか
・新規プロファイルではどうか

この辺りを行ってみて、結果を書き込んでいただけないでしょうか。

あと、お使いになられているセキュリティソフトで Cookie やキャッシュを削除するようなものはありませんか？
例えば、私がインストールしている Intego NetBarrier X4 だと自動的には削除しませんが、コントロールパネルからブラウザのキャッシュや Cookie を削除することが出来ます。

返信ありがとうございます！
Hide様からの返信に気付く前にプロファイルを新しくして試してしまったので、
全てを試すことはできなかったのですが、
Cookieを削除してFirefoxを再起動して試してみることでは改善されませんでした。
その後、意を決してプロファイルを新しく作り直して試した所、
Firefoxを再起動しても正常にCookieが保存されるようになりました。
先程ブックマークの復旧ややアドオン等の設定も終わり、無事元の状態に戻った所です。
どうもありがとうございました！