We study in detail the quasinormal modes of linear gravitational perturbations of plane-symmetric anti-de Sitter black holes. The wave equations are obtained by means of the Newman-Penrose formalism and the Chandrasekhar transformation theory. We show that oscillatory modes decay exponentially with time such that these black holes are stable against gravitational perturbations. Our numerical results show that in the large (small) black hole regime the frequencies of the ordinary quasinormal modes are proportional to the horizon radius \(r_{+}\) (wave number \(k\)). The frequency of the purely damped mode is very close to the algebraically special frequency in the small horizon limit, and goes as \(ik^{2}/3r_{+}\) in the opposite limit. This result is confirmed by an analytical method based on the power series expansion of the frequency in terms of the horizon radius. The same procedure applied to the Schwarzschild anti-de Sitter spacetime proves that the purely damped frequency goes as \(i(l-1)(l+2)/3r_{+}\), where \(l\) is the quantum number characterizing the angular distribution. Finally, we study the limit of high overtones and find that the frequencies become evenly spaced in this regime. The spacing of the frequency per unit horizon radius seems to be a universal quantity, in the sense that it is independent of the wave number, perturbation parity and black hole size.