When I worked at Scalr, we used Chef's Omnibus (https://github.com/chef/omnibus) to create "full stack" RPM and Deb packages, which basically include all your dependencies all the way down to libc (meaning libc is your only dependency) in a single "fat" package (this does mean you have to keep tabs on security updates to your dependencies; that's a pretty big tradeoff). Chef (obviously) does the same thing for their Chef server.

We'd originally tried shipping the software as a package with dependencies on other OS packages (installed using shell scripts originally, and then using Chef), but this never really worked: every enterprise would have slightly different OS configurations and the install scripts would practically never work.

We did try Docker as a deployment method, but most customers weren't comfortable with it for production deployments (or simply had systems that were too old to run Docker on). Also, orchestration tooling wasn't there yet. Bear in mind that this was a year ago, though.

--

Locked-down VM images (virtual appliances) are to my knowledge quite common as well (e.g. that's how Github enterprise is distributed). With more and more customers using AWS (and other cloud providers), cloud images are becoming another viable option.