Of course there was a piece of malware involved.
A Linux binary called dt_ssh5 did the grunt work.
The dt_ssh5 file was found installed in /tmp on affected systems, likely because the /tmp directory tends to be world readable and world writeable.
Three basic lessons:
Stay away from guessable passwords
Watch for weird files (stuff you didn't put there yourself) anywhere in your file system, even in /tmp.
Internalize the fact that PermitRootLogin yes is a bad idea.
We'll be back with more later, but first -