Pues lo que te han dicho, para programas comunes no tendras problemas en econtrarlos en el synaptic.
Si no lo encuentras de esa forma, lo mejor que puedes hacer es buscar el .deb, y ir resolviendo las dependencias a mano, si hace falta.
Y como ultimo recurso, compilar tu el programa. Yo nunca he conseguido hechar a funcionar un programa que tubiese que compilar. Aunque supongo que en tu distribucion debe ser mas facil conseguirlo, que en mandriva, al menos esa es mi experiencia.