In a recent letter [Chem. Phys. Lett. 291, 101 (1998)] we presented a semiclassical methodology for calculating influence functionals arising from many-body anharmonic environments in the path integral formulation of quantum dynamics. Taking advantage of the trace operation associated with the unobservable medium, we express the influence functional in terms of a single propagator along a combined forward-backward system path. This propagator is evaluated according to time-dependent semiclassical theory in a coherent state initial value representation. Because the action associated with propagation in combined forward and backward time is governed by the net force experienced by the environment due to its interaction with the system, the resulting propagator is generally a smooth function of coordinates and thus amenable to Monte Carlo sampling; yet, the interference between forward and reverse propagators is fully accounted for. In the present paper we present a more elaborate version of the semiclassical influence functional formalism, along with algorithms for evaluating the coherent state transform of the Boltzmann operator that enters the influence functional. This factor is evaluated by performing an imaginary time path integral, and various approximations of the resulting expression as well as sampling schemes are discussed. The feasibility of the approach is demonstrated via numerous test calculations involving a two-level system coupled to (a) a dissipative harmonic bath and (b) a ten-dimensional bath of coupled anharmonic oscillators.