First of all an overview of the Interfaces
Map: have key and a value. With the key the value can be looked up. These keys are unique so there is no duplication (at least not for the keys, you could insert to identical objects as long as they are stored with a different key).
You've got general Map which are not sorted, no garantee of any order. If order is needed you must look for a SortedMap implementation.
Remember that order is defined using the compareTo() method (Comparable). Custom objects need to implement this. The uniqueness is defined using the equals() method of java.lang.Object (which all objects extend). Good to know is that default implementation checks the actual instance of an object (=memory address). Override the equals() (and hashCode()) method to meet your needs. By example a user could be compared by email, etc...
When you add a custom object to a sorted collection while it doesn't implement Comparable you'll get the following error:
Exception in thread "main" java.lang.ClassCastException: NoComparable cannot be cast to java.lang.Comparable
Collection: only store values so no way to lookup. This means you would have to iterate the elements in order to find a specific one.
No keys here, uniqueness depends: Set and SortedSet can't contain duplicates, List can. The List is actually indexed, so the order is the one in which elements were added. The Set has no order what so ever, the SortedSet orders it's elements with the compareTo() method (or a given Comparator).
A note on sorting and performance: Use it only when really needed. A sorted collection has it elements sorted all the time. This means on every update (adding, removing, changing an element) the collection needs to resort and that takes some time and memory. Another solution is to use an unsorted collection and sort it only when presenting to the user.
This is only a quick start, you now only got the interfaces. You still need to find the right implementation. Look at the javadocs and don't forget that besides sun there is also the jakarta commons collections... More might follow.