  Hessenberg varieties are a family of subvarieties of the flag variety,
including the Springer fibers, the Peterson variety, and the entire flag
variety itself. The seminal example arises from a problem in numerical analysis
and consists for a fixed linear operator M of the full flags V_1 \subsetneq V_2
>... \subsetneq V_n in GL_n with M V_i contained in V_{i+1} for all i.
  In this paper I show that all Hessenberg varieties in type A_n and semisimple
and regular nilpotent Hessenberg varieties in types B_n,C_n, and D_n can be
paved by affine spaces. Moreover, this paving is the intersection of a
particular Bruhat decomposition with the Hessenberg variety. In type A_n, an
equivalent description of the cells of the paving in terms of certain fillings
of a Young diagram can be used to compute the Betti numbers of Hessenberg
varieties. As an example, I show that the Poincare polynomial of the Peterson
variety in A_n is \sum_{i =0}^{n-1} \binom{n-1}{i} x^{2i}.
