1.Самый простой способ это пропарсить
/var/lib/dpkg/available с помощью sed,perl,awk
2. В kde есть морда которая называется kpackage,
но "Шурик, это же не наш метод" (c)
Потому, что ты первый, кому это понадобилось :) Если есть желание, оформи полученный скрипт пакетом и предоставь общественности, может ещё кому надо будет :)