We study the effective pair interaction potentials and the resulting phase behavior, percolation transitions of nanorods dispersed in solutions of adsorbing polymers. We use polymer self-consistent-field theory in conjunction with the Derjaguin approximation to compute the polymer-mediated orientation-dependent pair interaction potential between cylindrical nanorods. A modified Flory theory and a simple analytical model are used to delineate the different equilibrium phases and the onset of percolation for nanorods in polymer solutions. Our results suggest that the topology of the phase diagram of a mixture of polymer and rods is highly dependent on the anisotropy of the rods, relative sizes of the rods and polymers, concentration of the polymer, and the strength of adsorption. For the case of nonadsorbing polymers, the polymer depletion-induced attractive interactions result in a large two-phase region which widens with an increase in the polymer concentration. Addition of adsorbing polymers is observed to lead to a richer phase behavior where at high polymer concentrations the polymer-induced repulsive interactions result in steric stabilization of the particles and lead to an isotropic-nematic transition which closely resembles the behavior for hard rod suspensions. As a model mimicking nanotube-polymer mixtures, we also discuss the influence of strong rod-rod van der Waals interactions on the stability characteristics.