Sorted // Ordered

Uma Collection Ordered é ordenada segundo algum critério. Esse critério define a ordem em que você vai iterar pelos elementos dela.
ArrayList, por exemplo, é ordenada pelo índice que é criado ou informado quando se adiciona um elemento.
O LinkedHashSet também é Ordered porque mantém a ordem em que os elementos são adicionados.

Já Sorted, significa que ela é classificada por uma ordem natural. Essa ordem pode ser alfabética (para Strings) ou numérica (para as Wrappers numéricas), ou uma ordem que você mesmo definir. Não lembro os detalhes exatamente, mas vc implementa a interface Comparable e utiliza um método para dizer qual dos dois Objects é maior.