I was reading in the Aug 07 MSDN magazine and came across an interesting article about when to use collections. I thought I would paraphrase the sections and add some more info to the article.

What is a Collection?
The basic function of a collection is to tie certain objects together as a group because the have some logical connection to each other.

When to Use a Collection?
One of the primary reasons for storing items in a collection is to enable easy iteration through all of the elements so as to allow an operation to be performed on each individual element. Here are some simple guidelines of when you should use a collection whenever at least one of the following statements are true:

Individual elements server similar purposes and are of equal importance

The number of elements is unknown or is not fixed at compile time

You need to support iteration over all elements

You need to support sorting of the elements

You need to expose the elements from a library where a consumer will expect a collection type.

Generic or Non-Generic
In the .NET framework 2.0 Microsoft introduced Generics. In .NET 1.x most the collection classes stored System.Object references which meant that every time you extracted an item out of the collection you would have to cast it back to its original type. By using generics you can avoid these issues. For example if you need a list of strings in your C# application you could use System.Collections.Generic.List this means everything in your collection is a String. So when you extract the item it will return to you as a String type.

Below is a list of collections replacements between non-generic collections to the new generic collections.

 Non-Generic Collections to Generic Counterparts
Non-Generic                        Similar Generic Type
ArrayList              List<T>
Hashtable              Dictionary<TKey,TValue>
SortedList             SortedList<TKey,TValue>
Queue                  Queue<T>
Stack                  Stack<T>
IEnumerable            IEnumerable<T>
ICollection            N/A (use IEnumerable<T> anything that extends it)
N/A                    ICollection<T>
IList                  IList<T>
CollectionBase         Collection<T>
ReadOnlyCollectionBase ReadOnlyCollection<T>
DictionaryBase         N/A (just implement IDictionary<TKey,TValue>
N/A                    SortedDictionary<TKey,TValue>
N/A                    KeyedCollection<TKey,TItem>
N/A                    LinkedList<T>

More details concerning the Generic counterparts

List<T>: It's a better ArrayList and will store items in an underlying array that maintains order. Adding items may require existing items in the underlying array to be moved to make room. Adding items at the end will not require any moves and will be very quick. You’ll want to use it for a majority of internal implementations whenever you need to store items in a container. You do not want to use it in public APIs.

Dictionary<TKey,TValue>: is just a strongly typed Hashtable. With some changes to the hashing algorithm, when you want additions, removals, and lookups to be very quick, and when you are not concerned about the order of the items in the collections, this gives you fast insertions and lookups. The changes between this and the System.Collections.Hashtable is the algorithms to deal with Hash Collisions. The Hashtable uses Probing and Dictionary<K,V> uses Chaining.

ICollection<T>: Extension of IEnumerable which it also exposes five new methods and two new properties, the first is Add, which is used to add a new element to a collection; Remove, which is used to remove an element; Clear, which is used to remove all elements; Contains, which tells us if an item is in the collection or not; and CopyTo which is used to copy items to an array. Two read only properties are IsReadOnly and Count.

ReadOnlyCollection<T>: is a much better ReadOnlyCollectionBase. It’s in System.Collections.ObjectModel namespace.

Queue<T> and Stack<T>: are equivalent to Queue and Stack. If your usage pattern requires few deletions and mostly additions and its important you keep it in order, you can choose a List. Lookup could be slow (since underlying array will need to be traversed while searching for targeted item) but you are guaranteed that your collection maintains order. Alternatively you can choose a Queue to implement a first-in-first-out (FIFO) order or a Stack last-in-first-out (LIFO). supports insertion at the end and removal from the beginning

SortedList<TKey,TValue>: See SortedDictionary as well. SortedList uses two separate arrays to maintain the keys and the values separately and to maintain them both in order (in the worse case you would have to shift all the keys and values)

SortedDictionary<TKey,TValue>: Uses a balanced tree (red-black tree) as the underlying data store; this provides faster insertions while maintaining items in a sorted order, but lookup will most likely be slower. Alternatively you can use SortedList<TKey,TValue>

IEnumerable<T>: is just like IEnumerable, but strongly typed. One difference is that IEnumerable<T> extends IDisposable.

IList<T>: is a strongly typed IList. It is Used in implementing Collection Interfaces: IList is an extension of ICollection. In Addition to everything that is in ICollection, it has IndexOf, Insert, and RemoveAt methods as well as an indexer that allows you to get and set any item in the collection. The IList interface is very useful when creating custom collections that allow you to add and remove items at will and get and set values of any item.

IDictionary<TKey,TValue>: It support the concept of using a key to store and locate items in the collection. In addition to all the items in ICollection, it exposes another Add overload that associates a key with the item that is added. The ContainsKey method will check for the existence of a particular key.

DictionaryBase: does not have a corresponding generic type. Simply implement IDictionary<TKey,TValue> if you need a custom dictionary.

KeyedCollection<TKey,TItem>: It’s a new collection which allows items to be indexed by both a key and an index. Use it to expose collections of items that have natural “names” (keys) from public APIs. You need to inherit from the collection to use it.

LinkedList<T>: Improved performance in scenarios where you need to maintain order yet still achieve fast inserts, LinkedList is implemented as a chain of dynamically allocated objects in comparison to List, inserting an object in the middle only requires updating two connections and adding the new item. Downside of a linked list from a performance point of view is increased activity by the garbage collector as it has to traverse the entire list to make sure object were not disposed of. Also large linked lists can cause performance problems due to the overhead association with each node as well as where in memory each node lives
Further Reading

When to Use Generic Collections
Visual Basic Generics Sample
Generic Collections
Visual C# 2005 (A Developer's Noteback)
System.Collections.ArrayList Performance Analysis
What are Generic Collections?