La solution de cris est valable, mais tu peut te passer de la compilation en deux étape en donnant tout les fichiers sources à gcc en même temps :
gcc -o liball.so -shared -fpic all.c a.c b.c c.c
Tu semble donner beaucoup d'inportance au fichier d'en tête. Mais sache que ceux-ci ne contiennent aucune information pour la compilation, seul les fichiers sources compte. Inclure, par exemple, a.h, b.h et c.h dans all.h n'est pas faux, mais si les fonction de all.c utilise les fonctions de ces fichiers source, mais pas les fonctions qui appelleront celle de all.c, alors c'est dans all.c qu'il faut inclure ces en tête et non pas dans all.h. En effet, tu va distribuer all.h avec ta bibliothèque, mais si tu ne distribue pas les autres en tête avec, ça vas poser des problème (tel que tu l'a fait pour l'instant).
Et pour ton problème plus directement, les fichiers sources n'ont pas forcément de fichier d'en tête associé, ou pas forcément avec le même nom, ou pas en seul, etc. Donc ce n'est pas parce qu'un fichier référence des en tête que gcc va être capable de trouver les fichiers sources qui contiennent le code correspondant pour le compiler. C'est ce qui explique qu'il manque des symbole dans ta bibliothèque.