Even if you are not looking for trouble and do not violate any known SEO rule (but only half of them), you still might have to experience the ultimate SEO nightmare - being excluded from Google's index. Although Google is a kind of a monopolist among search engines, it is not a bully company that excludes innocent victims for pure pleasure. Google keeps rigorously to SEO best practices and excludes sites that misbehave.

Not Present in Google's Index

First, it is necessary to clarify that the fact your site is missing from Google's index can mean two things:

a. You have not been included yet, though you have submitted an inclusion request. As described in the Google Sandbox article, it is normal to have to wait some time before being indexed for the first time. You can't to anything to speed the process but wait.
b. You have been excluded from Google's index because of violation on your site. As said, this is a real nightmare for any SEO and you will need to take some steps to correct this most unfavorable situation. The rest of the article explains how.

Why Does Google Exclude Sites?

There are many reasons that can make Google exclude your site(s) and all these reasons are related to a violation of some kind. For instance, your sites are over-optimized and this makes them very suspicious. Over-optimization has many faces and you can have a look at the Optimization, Over-Optimization or SEO Overkill? Article to get some ideas of practices that you should avoid.

Besides over-optimizing the onsite content, some of the other reasons for being excluded from Google are SE spamming, hidden text, hosting illegal content, linking to bad neighbors, inter-linking, etc. There is no an exhaustive list of SEO sins that Google does not tolerate, nor you'll get a letter from Google to inform you that you have been a bad boy and that's why you have been kicked out of its index but if you resort to any forms of SEO manipulation and you attempt to mislead search engines, you might expect that sooner or later you will have to deal with reinclusion.

Reinclusion Steps

After you discover that you have been excluded from Google, the first step is to analyze why. You need to know what made them angry with you and correct your mistakes. Check for links to link farms and bed neighbors, for doorway pages and keyword stuffing. It is unlikely that you don't know your own sins.

Next, you have to contact Google with a reinclusion request. Go to Google Sitemaps and from the Tools menu on the right, select Submit a Reinclusion Request. On the next screen, read carefully the instructions and explanations, fill in the required data (you may want to have a look at the next section - Reinclusion Tips for ideas what to write) and submit your request.

After you submit your inclusion request, there is nothing more you can do than fix your errors (if you have not already done it) and wait patiently for the answer.

Though the process of submitting a reinclusion request is pretty straightforward, there is some general advice, which can help you. The following tips can improve your chances of success.

Reinclusion Tips

Admit your errors and fix them
This has already been said but it is a big mistake to write to Google and play innocent. You can lie to yourself but this way you will not convince them that you are a martyr who has been suffering because of their cruelty. And above all - fix your mistakes before you submit the reinclusion request. It is a very stupid situation to have your errors unfixed and wait for reinclusion because you will simply never get reincluded this way. What is more, you are undermining your chances for success in the future as well.
Be polite.
The worst mistake you can make in your reinclusion request is to be rude. Threatening Google with lawsuits or hinting that you might boycott their AdWords program in revenge for being excluded from their index is a deadly mistake. Anyway, Google are not obliged to provide you with free traffic, so being included in their index is not a special privilege they had granted you for your AdWords money.
Look at their Webmasters Guidelines.
It is unlikely that they have changed them recently and you do not comply with them anymore but it does not hurt to double check that you have done what Google recommends to do.
Don't spam them.
Google receives heaps of e-mails and it is not possible to answer each incoming e-mail an hour or so after it had been submitted. Bombarding Google with tons of e-mails (even polite ones) could only make your situation worse.
Is it your first time?
Google may not keep statistics of its recidivists but if it just happens that your site gets bans several times a year, this gets very suspicious. If you are banned for the first time, you can account on amnesty. But if you have been banned many times, you can be out of luck with reinclusion requests about the same site.
Reaasure them that it is not going to happen again.
This is also very important because if Google get the impression that you violate their rules very often, they might be reluctant to reinclude you. In some cases, when it was not your personal fault - e.g. webmaster you hired sent many spam letters or your site got hacked, you can explain what happened, giving a detailed timeframe of the events.
Consider AdWords
If you really rely heavily on traffic from Google, consider buying AdWords. This is not a blackmail (we ban you, you pay for AdWords) because many sites just do not pay for AdWords but rely on other traffic-generating schemes instead.