I could be wrong, but I believe Shodan actually portscans the entire internet, whereas Google only crawls known URLs. They also index HTTP headers, which Google doesn't do.
It's run by our very own achillean: https://news.ycombinator.com/threads?id=achillean