Mariya Moeva and Bergy Berghausen of Google posted an excellent step by step instruction manual and video on when and how to submit a Google request for reinclusion in Google. In short, the steps are as follows:
(1) Login to Webmaster Tools and check for any crawl errors, such as “URL unreachable” or “URLs restricted by robots.txt” errors. If you find those errors, dig deeper and see if you can open up those access errors. If those are not your issues, proceed to step two.
(2) Check in Webmaster Tools the Message Center for any notifications of site issues. If there is something there, then follow those recommendations.
(3) Then you want to review the Webmaster Guidelines and patch up any issues with your site that may have caused your site to be de-indexed form Google.
(4) Finally, go back to Webmaster Tools and submit a “reconsideration request,” but only after you are confident your site is in compliance with Google’s Webmaster guidelines.
Here is a fun video to watch that demonstrates everything listed above: