<p>It is unclear to me from the <a href="http://msdn.microsoft.com/en-us/library/system.icloneable.aspx" rel="nofollow noreferrer">MSDN documentation</a> if I should provide a deep or a shallow clone when implementing ICloneable. What is the preferred option?</p>

Clones are deep by default, thats the naming convention
and copy constructors can be shallow if they want, for performance reasons.
Edit: This naming convention goes beyond boundaries, its the same for .Net, Java, C++, Javascript, etc... the actual source is beyond my knowledge but its part of the standard Object Oriented lexicon, just like objects, and classes. Thus MSDN doesn't specify implementation because its a given by the word itself (of course lots of newcomers to OO languages don't know this, and they SHOULD specify it, but then again their documentation is quite frugal anyways)