A dense matrix is distributed for parallel computation column-wise, then multiplied from left & right by sparse matrices. What would be appropriate c++ libraries for these tasks?
For dense distributed memory linear algebra, you can't do better than Elemental these days. Although, it does not currently handle sparse matrices, I believe. Dense-sparse operations will probably require you to do some custom coding.
The ScaLAPACK library is designed for dense matrix operations on distributed memory machines. It will still work on a shared-memory machine though, provided that you have MPI installed (installation requires mpicc and mpif77 compilers on linux). I haven't used it before, so I can't attest to its user-friendliness.
I would day it definitely depends on the parallelization architecture and what you want. If using shared memory CPU's, probably Elemental even though I have not used it. Note that PETSc also has tools for sparse matrices. But if you really need it to go as fast as you can, and the sparse matrices have some known structure that you can take advantage of, then I would write the whole thing using MPI. In my experience that is always much faster, but also requires more work. So it depends on your needs and time to code.
If you want to go with GPU's, nvidia has a sparse matrix library that you could try using CUDA.
CUDA 5 also let's you do some kind of mpi+cuda, so you can have a clusters of gpu's, but I have no idea if the sparse-matrix libraries are capable of that but I don't see why not. It's worth to take a look at. But again, if you need it to fly, I would make my own code.