The copy constructor given by @Stephen C is the way to go when you have a Set you created (or when you know where it comes from).
When it comes from a Map.entrySet(), it will depend on the Map implementation you're using:
findbugs says
The entrySet() method is allowed to return a view of the underlying Map in which a single Entry object is reused and returned during the iteration. As of Java 1.6, both IdentityHashMap and EnumMap did so. When iterating through such a Map, the Entry value is only valid until you advance to the next iteration. If, for example, you try to pass such an entrySet to an addAll method, things will go badly wrong.
As addAll() is called by the copy constructor, you might find yourself with a Set of only one Entry: the last one.
Not all Map implementations do that though, so if you know your implementation is safe in that regard, the copy constructor definitely is the way to go. Otherwise, you'd have to create new Entry objects yourself:
Set<K,V> copy = new HashSet<K,V>(map.size());
for (Entry<K,V> e : map.entrySet())
copy.add(new java.util.AbstractMap.SimpleEntry<K,V>(e));
Edit: Unlike tests I performed on Java 7 and Java 6u45 (thanks to Stephen C), the findbugs comment does not seem appropriate anymore. It might have been the case on earlier versions of Java 6 (before u45) but I don't have any to test.