Определить зависимости бинарника от packages в Linux(Ubuntu)?
dpkg -S /usr/lib/libnuzhnayaliba.so покажет в какой пакет она входит. Это можно использовать.

Однако я бы сделал пакет, при правильном написании системы сборки в debian/rules обязательно есть команда dh_shlibdeps (могу ошибаться с точным названием), которая включит нужные зависимости. Установка пакета в этом случае может выглядеть так:

dpkg -i proga_1.0_i386.deb
apt-get install -f

При первой программе ругнётся — это нормально. Вторая пофиксит зависимости и выполнит postinstall первой.
У вас есть какой-то бинарник, а не нормальный пакет, который вы собираетесь «разворачивать»? Зависимости по уровням версий есть только на уровне работы с пакетами, при работе с бинарниками можно ориентироваться только на версию ABI. Лучше свяжитесь с тем, кто компилировал бинарник, чтобы уточнить с какими версиями библиотек он линковался.