Earlier quoted context omitted.
Disable SSLv2 everywhere.
To make it more clear: According to the info page, I can disable SSLv2 on OpenSSL only by installing a newer version of OpenSSL, that is not available on Debian (as I found). (I also updated my original post)
Debian practically never updates to new versions of software (until you upgrade Debian). Instead they "backport" security fixes into the older software versions, preserving the old version numbers but adding some stuff on the end to reflect Debian's changes. The intent is that you get "only" security fixes, never features or improvements.
So when you see "OpenSSL-1.0.c-stuffgoeshere" you are not looking at "OpenSSL" openssl anymore, but a version that Debian customized, probably to add security fixes. I say "Debian" here, but really most distros do it (RHEL, Ubuntu, CentOS, etc.) I'm just not familiar enough with their processes to comment specifically.
Debian has disabled SSLv2 in its OpenSSL packages since 2010 [0], and if you are running a Debian OpenSSL version later than 1.0.0c-2 your OpenSSL version is not vulnerable. The current version of OpenSSL in stable is 1.0.1k-3+deb8u2, so unless your server has been under a rock for 5 years you should be fine. And if it's been under a rock for 5 years you have a lot of security vulnerabilities to be worried about.
Of course you may have installed OpenSSL from somewhere else, or you may be using some other software for SSLv2 that doesn't involve OpenSSL at all. So merely upgrading your OpenSSL version is not a silver bullet, you need to think about every TLS deployment you have and how it might be used.
More broadly, use this vulnerability as a wakeup call to learn about "where your software comes from", because everybody has a role to play in staying secure, including users. Debian is maintained by volunteers; you might be happier with a commercial vendor who guarantees response times. Debian backports security fixes; you might be happier with a distribution that upgrades to new vendor versions which may have avoided the confusion here.
[0] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=589706