Now we come to the heart of things: what goes into a reinclusion request. Fundamentally, Google wants to know two things:
1) that any spam on the site is gone or fixed, and
2) that it’s not going to happen again.

I’d recommend giving a short explanation of what happened from your perspective: what actions may have led to any penalties and any corrective action that you’ve taken to prevent any spam in the future. If you employed an SEO company, it indicates good faith if you tell us specifics about the SEO firm and what they did–it assists us in evaluating reinclusion requests. Note that SEO and mostly-affiliate sites may need to provide more evidence of good faith before a site will be reincluded; such sites should be quite familiar with Google’s quality guidelines.

http://www.mattcutts.com/blog/reinclusion-request-howto/