Welcome to Server Fault. In general this type of question is not on-topic here. It is expected that most sysadmins will have already faced this issue before they became a sysadmin through tinkering with their own workstations. However, sysadmins coming from a Windows background may not have faced this, so here are some things to consider:

Why not use a package manager to install software on your server?

Package managers such as yum or apt handle these dependencies for you. In addition they can also be used to manage updates of the software on your server. Most flavours of *nix will have a package manager installed by default, especially on VPS that come with the OS pre-installed. If you are really new to this, use one of these on your production system, and save adventures in compiling or installing bleeding edge RPMs for your test environment.

But I am required to use a more up to date package than what is available in my package manager!

Most package managers can be configured to use different repositories — you may find that there is one that provides the version of the package that you need, and still allows you to take advantage of your package manager's functions.

The package I need is not available through any repos or package managers

In that case you probably do need to figure out the dependencies (or suck it up and use a more stable/common version of the software). You should probably do the following in a test environment and take careful notes of what you do:

• Make sure to read the documentation for the software you are installing — this will probably list what you need to install first, but not what is required for that software.
• Use your package manager to install the things that are required — in most cases these will be available.
• Once you have completed this, try installing.
• If you still see messages about missing dependencies, take a note of all of them, and again try to install as many as possible using your package manager.
• If a dependency is not found, you have to consider it a subtask and treat it recursively (find the source tarball, find dependencies, install).
• It's an iterative process.

I'm still having problems!

If you have followed all the above steps and are still having trouble then you may have come across some weird issue that other Server Faulters may be happy to help with. Create a new question, giving details of what software you are trying to install, which version, and the exact error messages you are seeing.

Specific advice for major package management systems

RPM (RHEL/Fedora and clones) and DEB (Debian/Ubuntu and clones) package management

• yum whatprovides filename is an excellent way to find the package that provides a specific file or library on a RHEL type system.
• Do not use ./configure && make && make install blindly if at all possible! Package management was invented for this very reason to prevent the awkward and unmaintainable mess that results from untraceable installation of many conflicting files.
• Many libraries are split into two parts: binary (shared objects, for instance) and development (headers). Thus, you'd need both libfoo and libfoo-devel (or -dev) packages.
• Consider using fpm (https://github.com/jordansissel/fpm) to convert tarballs into neat RPMs and DEBs
• If you are rolling your own packages, YOU are the person responsible for their updates, testing and maintenance. If you have got no infrastructure for that, you are definitely aiming too high.

Finding dependencies by file name for RPMs

http://rpmfind.net is a good place to look for names of packages if you know the name of the file the installation procedure is complaining about. Matching and mixing packages from different distributions is not recommended, though.