Remove all the rubbish links pointing to your site. Add some fresh "good" content. Clean up the site (broken links, keyword stuffing etc etc). Get some proper links from quality sites. Links with a good range of anchors. Some (and I mean only some) social links. Add some fresh "good" content. That's a start.
Try to get the nofollow links for example from comments. Start to add more valuable content to your web page. Do it regularly.
If you have not been "overoptimizing" your site then Penguin shouldn't have hit you at all. The goal of all the google updates is to enable the sites with good content to rank above sites with bad content who just spam their link all over the place. Just make your site as "normal" as possible, write content, do not always use the same anchor text when linking your site, etc ...
Please try to avoid the following 4 things - 1. Aggressive exact-match anchor text 2. Overuse of exact-match domains 3. Low-quality article marketing & blog spam 4. Keyword stuffing in internal/outbound links
Start fresh following the advice of someone who has proof he has done it. That's the advice that works.
Whether believe me or not, if my site is get penalized then I would start my work freshly with new domain, this is the way now I'm seeing.
Diversification would work but it would take time...and there is no guarantee as well. So you can diversify of course but you have to do it with fresh work, new domain.
you need to diversify your link building. use a variety of keywords for your anchor text and not just the main one over and over again. keep away from low quality sites which are just link farms. on page keyword stuffing is also a bad idea.
That is a good summary and about covers it. To recover, just start building a fantastic website with regularly updated content that people LOVE to visit. Get that part right and all the SEO stuff is not something you think about all that much.
You should send an apology mail to Larry Page explaining him that you are a small blogger and wish to keep the site running on google, also mention that you can pay some some 10-20 dollars penalty fees to get your site on Google search results.
Google Penguin update is mainly for back links, so obviously you should concentrate on making good, quality and niche back links for your website.
Add a blog and update content on daily basis, it will give Google an idea that your site is quality one.
Yes, Social Media is a good resource now a days to attract your targeted visitors. You may get good traffic from this useful resource.
What I don't get is people are saying don't use the same Anchor text for inbound links or keep it varied. Lets take Google as a website, most people that link to Google will use either one or two terms the first being "Google" and the second probably being "Search Engine". Cleaning up Outbound links, broken internal links, image links and reducing on page SEO seems to be the way forward, however for me after making some changes here and there I haven't seen much change in the SERPs they are still a bit of a mess.
Penguin deals with bad and spammy backlinks and thousands of links with same anchor text. So you should analyze you linking profile and then remove such links that are against Google's guidelines. Also keep on building new quality backlinks.