  We consider bases for the cohomology space of regular semisimple Hessenberg
varieties, consisting of the classes that naturally arise from the
Bialynicki-Birula decomposition of the Hessenberg varieties. We give an
explicit combinatorial description of the support of each class, which enables
us to compute the symmetric group actions on the classes in our bases. We then
successfully apply the results to the permutohedral varieties to explicitly
write down each class and to construct permutation submodules that constitute
summands of a decomposition of cohomology space of each degree. This resolves
the problem posed by Stembridge on the geometric construction of permutation
module decomposition and also the conjecture posed by Chow on the construction
of bases for the equivariant cohomology spaces of permutohedral varieties.
