Google Web Search API has been deprecated and replaced with Custom Search API (see http://code.google.com/apis/websearch/).
I wanted to search the whole web but it looks like with the new API only custom sites can be searched.
Is there a way to search the whole web programmatically? I was able to query the old API using JSON from a Java program.
Gigablast offers a cheap web search API: http://www.gigablast.com/searchfeed.html
Google Custom Search (as advocated in the top rated answers) works well, but is very expensive, compared to its competitors (below) or compared to other Google API's. It has a small free tier (100 queries/day) and a very high price of $5 per 1000 query.
They offer the option to upgrade to Site Search, which has slightly better prices, but that is meant for searching one site (your own), so it is really something quite different - not an upgrade.
The main alternatives seem to be:
Bing Search API
https://datamarket.azure.com/dataset/5BA839F1-12CE-4CCE-BF57-A49D98D29A44
Which has a free tier of 5000q/month, and prices starting at 5 query per penny, and no hard limit.
UPDATE: At the end of 2016 this API was shutdown in favour of its Azure counterpart "Cognitive Services Bing Search API":
https://azure.microsoft.com/en-us/services/cognitive-services/search/
See here for a pricing chart, which starts at US$3/m for 1,000 transactions. Unless I'm missing something it is quite expensive.
Yahoo BOSS Search API
UPDATE: Was discontinued on March 31, 2016. http://developer.yahoo.com/boss/search/
With prices starting at about 12 queries/penny for whole web searches.
And some I haven't heard of before:
http://www.gigablast.com/searchfeed.html
http://www.faroo.com/hp/api/api.html
http://www.commoncrawl.org/
http://www.entireweb.com/search_api/implementation/
[discontinued - as pointed out below]
There is a bit of discussion of some of these on this SO post.
[got closed for being off-topic and is now gone]
I have just come across this from Common Crawl.
http://www.commoncrawl.org/
Might be the answer we are all looking for!!
Faroo has a free Web Search API
You can create "everywhere" custom search engine right from the Google Custom Search homepage ( http://www.google.com/cse/ ). You should just click 'advanced', during adding new engine. There you can provide Schema.org site type. 'Thing' is most generic type, which covers all the web.
You could just send them through like a browser does, and then parse the html, that is what I have always done, even for things like Youtube.