This morning jobs includes sorting out a site that has been removed from Google index. Having some experience with clients turning up with banned sites I thought it might be worth sharing some tips.
However my number 1 tip is, if you don't have a background in SEO and a background in server side scripting and administration employ a
consultant (blatant plug) its really worth it in the long run, the longer your site is off the index the more business your losing.
Of course this is an SEO forum so most here will feel they have the above requirements

Note: Google does not remove sites lightly, its important to understand why the site has been banned, if the site is suddenly dropped its worth investigating the possibility of a hack, or that consultant you hired wasn't quite as good as you thought. Either way if your site is your business then you need to approach this in a very methodical manner, after all you need to prevent it happening again and you may wish to take legal action.2. Take the site off-line, place a maintenance notice up, explaining their is a technical issue but don't go into details, make sure your redirecting all traffic to the notice. Make an initial backup copy of the site including databases.
Do not delete files on the server until you have found the problem, though you may wish to do a global chmod on the site to prevent accidental execution (though make sure your notice and .htaccess can be used )
3. Create two folders, and subfolder with the same structure as your site, one is your good folder the other quarantine, next sort through the files moving files you do not recognise or that appear to have changed significantly into the quarantine folder. You can look at these files later, and see what they do.
3. If your using a CMS then execute the sql query calls from the index to recreate page content, otherwise open the html files individually, and remove all external links within content, this includes advertisement and other javascripts. Make sure the page does not call a cgi script.
This may seem harsh but you need to prove to to Google that you have taken extreme measures to get the site clean, after re inclusion you can always add the scripts back. 4. For each page, check for hidden text, keyword stuffing is a traditional bad technique used by "idiot practitioners" multiple subjects etc. Go through and strip out all but content and basic styling.
5. Rebuild your site using only static pages, based on what you have cleaned I suggest only putting up a temporary mini site of 6-10 pages cleaned and static.
6. Now is the time for a decision, 1) Get the site up and running and put it down to bad luck or launch an investigation. The reason this is an issue now is up until this point we haven't touched the server other then to "make safe" however if we delete the site and upload the mini site we will have a harder time making a legal case. Now in most cases their will be no such need but occasionally it could be important to preserve the evidence. I'm going to presume you just want to get your site back in Google rather then forensic investigation.
7. Delete the site, drop the database, and change passwords on everything on the server. The upload your mini site and check its working, remember it has no outgoing links, no advertisement scripts and is static html.
8. Apply to Google for re-inclusion
http://www.google.com/support/bin/request.pyMake sure to indicate all the problems you came across, if you haven't yet found the source of the problem, explain that the mini site has been built from scratch and the old site removed for investigation. Be apologetic and friendly the person on the other end is a human, so treat them as such, but remember just like in law Google believes ignorance is not an excuse, so try not to whine to much

Update: You can now use the webmaster console to make such requests http://www.google.com/webmaster site needs to be verified9. The response, normally will return pretty quickly hopefully it will be positive but regardless its dialogue take anything they say on board and answer questions truthfully it may take 3 or 4 emails before you get a yes.
10. Wait for the spiders to have passed before making changes, while your waiting its time to track down the problem if you haven't already start looking through your quarantined files, and the rest of the site, next look through your external links, treat this time as a good site evaluation period, change your template and clean up the content, check your links and all your scripts.
The above is a lot of work but is the only way to really have a chance of re-entry unless you know what the problem is...
The other solution is to simply shut down the site, sell or ignore the domain and start again. In many cases this is the easiest option but not a very satisfying solution.
If you are getting a consultant in to help, make sure they have worked on re-inclusions in the past and for the right reasons (i.e clients have come to them post the event!), check that they have a technical background, sorry but most SEO's don't have the server side experience to do this sort of work and certainly not at the level required should the client wish to press charges.
Finally beware companies that guarantee successful re-inclusion, after all the final say is a human in an office in Google not the SEO company

however most companies will have very high success rates, and will always offer you written reports which you can submit to Google and others as proof of work done.
So that's my bit over hope it helps a few of you, I'm guessing like most things there are many ways to do this, and the above is a simplified method we use, though it varies depending on what the client wants done of course.
Penalties as opposed to banningGoogle often applies penalties rather then actual bans again this is not something they do likely but still it might happen the most high profile cases have included BMW (For IP Cloaking - Resolved) and John Chow (Paid Links) who no longer
ranks for his name. These penalties are manual and therefore reversible your best bet is to correct the problem and contact Google via webmaster console. Interestingly these style of penalties are normally against certain keywords so many sites don't notice the penalty instantly as their long tails are still getting searches. Manual penalties also don't automatically appear in Google webmaster centre so you won't have an idea that its happened.
Moving Domains with penaltiesManual penalties are applied to a domain, if you move the domain and redirect using a 301 redirect a manual penalty does not appear to move with it. However algorithmic penalties do, this is because they are applied by the search engine itself as it crawls if the problem is still there it still gets flagged. At least one site owner has reported that after a short period of time a manual penalty was reapplied this could be due to "being caught" again or through some sort of manual check.
Getting info from GoogleGoogle webmaster centre now will notify you of any penalties on a given verified site via a new message area.
See search engine land report for more details