First, you need to find out why you’re in it. That’s easier said than done, here are some ideas:

Duplicate Content - take someone elses content, get sent to Google Hell (Supplemental Results)
No Content - create pages with no content (remember the days of directories that would create 1 million pages with only 100 listing?) - empty pages get sent to Google Hell.
Orphaned web pages. Pages that no one links to, including yourself.
I can vouch for these. And keep in mind that duped content can be from copying yourself, such as having a mirrored site, for example.

So how do you get out?

If you stole content - change it.
If there’s no content - add some.
If it’s orphaned - link to it.
But once you’ve changed what’s causing it, you’ve got to get Google to come back around. I agree that the best way to do that is to create a Google sitemap and to ping Google with it.