Google will label sites in their search results as harmful, when the site is believed to have malware on it. The last thing Google wants to do, is help an unsuspecting searcher land on a web page that can infect your computer. So Google takes a proactive approach to discovery and labeling malware results.
But sometimes, your site can be found to have malware. Malware can get on your site through being hacked or through third party code. If you find this label on your site, you need to remove the malware from your site and notify Google that it has been removed.
After it is removed, go to Google Webmaster Tools and there will be a place to request a review. Go through that process and then hopefully, within a few hours, that label will be removed.
Google has a detailed post on this at the Webmaster Central Blog. That post and in a recent thread at Google Webmaster Help, it says, it typically takes hours to remove the label, but can take as much as a day.
Webmasters are eager to have a Google malware label removed from their site and often ask how long a review of the site will take. Both the original scanning and the review process are fully automated. The systems analyze large portions of the internet, which is big place, so the review may not happen immediately. Ideally, the label will be removed within a few hours. At its longest, the process should take a day or so.
Forum discussion at Google Webmaster Help.