Here is how I understand supersedence in SCCM, or how an application team would go about working with supersedence.

1. create new application, version 2, create supersedence in application version 2 to supersede version 1

2. remove all deployments of application version 1.  How would a client know how to behave if it had version 1 and version 2 assigned as required

3. retire version 1 of the application

4. deploy version 2 of the application.

So how does this work with dependencies?  If I have version 1 as a dependent on say 37 different applications, do I need to manually remove that dependency and add version 2 as a dependency?  is this taken care of automatically (I don't think so, but I am not sure)

The behavior for superseding a dependent application is slightly changed with the latest service pack. Please refer to this article for the expected behavior: https://technet.microsoft.com/en-us/library/gg682071.aspx