It works by scanning the entire Internet and parsing the banners that are returned by various devices. Using that information, Shodan can tell you things like what web server (and version) is most popular, or how many anonymous FTP servers exist in a particular location, and what make and model the device may be.