Com base na resposta de Riccardo Murri, consegui determinar todos os arquivos jar necessários para o caminho de classe:
java -cp /usr/share/java/axis.jar:/usr/share/java/commons-logging.jar:/usr/share/java/commons-logging-api.jar:/usr/share/java/commons-logging-adapters.jar:/usr/share/java/commons-discovery.jar:/usr/share/java/jaxrpc.jar:/usr/share/java/wsdl4j.jar org.apache.axis.wsdl.WSDL2Java foo.wsdl