Step 1: Install the managed package (the "base" package) into a new developer edition.
Step 2: Give the new developer edition a new namespace, create the new managed package (the "extension" package), and upload that package.
Step 3: Done.
Some notes are worth pointing out here. The extension package will implicitly link itself not just to the base package, but also the version of the base package, on a per-upload basis. For example, if the base package is 1.25 and the extension package is 1.2, then the extension version 1.2 will be linked to base package 1.25, so you can't install 1.2 in an org with an older version (say, base version 1.24).
The linkage only occurs if you explicitly reference any element in the base package, such as a field, object, or class. Standard fields and objects do not count. The base package isn't ever allowed to reference the extension package explicitly, and so will need to use dynamic references and Apex Code. Keep this in mind when building your base package.
Be sure to use global interfaces and classes in the base package if the extension package needs to reference those items in the base package. You won't be able to easily remove these classes and methods later, so choose carefully. Once a version of the extension is linked to a version of the base package, you can't ask for a rollback of the base package to an earlier version than was linked, so also keep that in mind as well.
For all of the cautionary tales I present here, I'd like to mention that it is deceptively easy to create extension packages, even to the point where you could do so accidentally. For example, if you install a third-party managed package, and you accidentally reference a member of that package, it automatically gets linked as a dependency as soon as you upload that version. You can rollback the upload by contacting support, but not if you install it in any customer's org. At that point, the link is permanent.
I would strongly recommend avoid installing any managed package that you don't intend to link to, in order to avoid the accidental links. This also means you should never install the extension into the base package's host organization. Always use an ISV throw-away organization to test and demo how the two packages interact with each other, so that you can uninstall and rollback (or patch) if something goes wrong.