There are only about four billions of possible IPv4 addresses, so trying them all is feasible, with enough bandwidth. There are available tools for that.
Shodan themselves document in their FAQ that they use some custom code:
A home-grown, distributed port scanner was developed for this project.
"Distributed" here means that connections are made from several machines, which seems not an issue since Internet-wide scanning is, by definition, an embarrassingly parallel problem.
A related case is the so-called Internet Census 2012 in which some unknown people repeatedly scanned for some vulnerable hosts (typically home routers still configured to accept default admin credentials) and temporarily hijacked the said systems to enlist them in a whole Internet scan on "most common ports" -- that's a case of a self-replicating botnet. They say that they reached 420000 clients under their control. For a complete Internet scan, each client only has 10000 IP addresses to try, so this can be done quite discreetly (say, 3 probed IP per second for an hour).