We report a nonlocal density functional theory (NLDFT) for polyelectrolyte solutions within the primitive model; i.e., the solvent is represented by a continuous dielectric medium, and the small ions and polyions by single and tangentially connected charged hard spheres, respectively. The excess Helmholtz energy functional is derived from a modified fundamental measure theory for hard-sphere repulsion, an extended first-order thermodynamic perturbation theory for chain connectivity, and a quadratic functional Taylor expansion for electrostatic correlations. With the direct and cavity correlation functions of the corresponding monomeric systems as inputs, the NLDFT predicts the segment-level microscopic structures and adsorption isotherms of polyelectrolytes at oppositely charged surfaces in good agreement with molecular simulations. In particular, it faithfully reproduces the layering structures of polyions, charge inversion, and overcharging that cannot be captured by alternative methods including the polyelectrolyte Poisson-Boltzmann equation and an earlier version of DFT. The NLDFT has also been used to investigate the influences of the small ion valence, polyion chain length, and size disparity between polyion segments and counterions on the microscopic structure, mean electrostatic potential, and overcharging in planar electric double layers containing polyelectrolytes.