As asymptotically perturbed cylinder is a manifold which, to the exterior of a compact set, is of the form R × M, where M is a compact manifold (with or without boundary), and for which the metric approaches the product metric as the axial variable tends to infinity. The properties of eigenfunctions of the Laplacian on asymptotically perturbed cylinders, with either Dirichlet or Neumann boundary conditions if the boundary is non-empty, are studied. For a large class of asymptotic perturbations, the eigenfunctions are proved to decay faster than the reciprocal of any polynomial as the axial variable tends to infinity. The decay estimates are then used to prove that the eigenvalues are of finite multiplicity, and can accumulate at the thresholds only from below. The results are shown to apply to a large class of acoustic and quantum waveguides.