The best way to deal with dependencies is with a package manager such as:
On Ubuntu: apt-get
On Red Hat / Fedora: yum
On Mac OS X: port
On Windows: cygwin
If you install software with a package manager, it will automatically fetch, download, and install any dependencies as necessary. These package managers support a huge number of popular open source projects, but not all projects are supported. Some of these package managers support creating custom package repositories, which allows them to be used for dependency management in-house, as well.
Unfortunately, there is no general way to get all the library dependencies of a Makefile (short of grepping for "lib", ".so", and "-l" which may give you spurious results); however, if you are installing an open source project, chances are that it is supported by a package manager on your system.