Потому что Set на то и множество, что порядок элементов в нём не определён. Кроме того, сет хранит каждый элемент только один раз, то есть код в любом случае неверный. Хранить в преференсах списки плохой тон. Но если надо, сериализуйте, например, в джсон, и потом десериализуйте обратно.
Нашел только putStringSet, поэтому загрузил лист в сет и записал. Когда вытащил обратно, понял, что порядок не такой как положил... а как сохранить arraylist?