こんな感じでgetStringSetで得た結果に直接要素を追加して、
putStringSetしてもダメっぽい。

SharedPreferences pref 
  = context.getSharedPreferences("name",Context.MODE_PRIVATE);

String key = "keyA";

// Setを取得する
Set&lt;String&gt; set1 = pref.getStringSet(key, new HashSet<String>());

// Setに文字列を追加
set1.add("追加する文字列");

// そのまま保存
SharedPreferences.Editor editor = pref.edit();
editor.putStringSet(key, set1);
editor.apply();

この状態でgetStringSetするとちゃんと設定されてて正常に動いているように見えるんだけど、 プロセスが再起動されたあとに消えてます。(2件目以降)

対応としては下記のように別のSetを作ってコピーしてあげるとちゃんと動いてくれた。

// Setをクローンする
HashSet<String> set2 = new HashSet<>();
set2.addAll(set1);

SharedPreferences.Editor editor = pref.edit();
editor.putStringSet(key, set2);
editor.apply();

モヤモヤしますな。