What is an efficient and elegant way to add a single element to an immutable set?

You might consider Sets.union(). Construction would be faster, but use slower.

public static <T> Set<T> setWith(Set<T> old, T item) {
  return Sets.union(old, Collections.singleton(item);
}

(com.google.common.collect.Sets & java.util.Collections)

Using Java 8 you can also use streams for that effect

Stream.concat(oldSet.stream(),
              Stream.of(singleElement))
      .collect(Collectors.toSet())

By the way since JDK 10, the Collectors also allow to accumulate to immutable types (the same as the ones created by the static factories like Set.of()) :

Stream.concat(oldSet.stream(),
              Stream.of(singleElement))
      .collect(Collectors.toUnmodifiableSet())

Not sure about performance, but you can use Guava's ImmutableSet.Builder:

import com.google.common.collect.ImmutableSet

// ...
Set<Integer> newSet = new ImmutableSet.Builder<Integer>()
                                .addAll(oldSet)
                                .add(3)
                                .build();

Of course you can also write yourself a helper method for that:

public static <T> Set<T> setWith(Set<T> old, T item) {
  return new ImmutableSet.Builder<T>().addAll(old).add(item).build();
}

// ...
Set<Integer> newSet = setWith(oldSet, 3);