Earlier I wrote a bit about what to do when your site has been hacked or spammed to the point where Google and Firefox start warning visitors away from your site. If you find you site deleted from Google search results completely, you’ll want to file a reconsideration request.
Luckily, the Google Webmaster Central blog has a great post on how to make a request to get back into Google. The post includes a step-by-step video. You can also check out the Google Webmaster Help group if you have questions.