How to scan a Mac for rootkits and other stealthy security hazards
I ended up using a second Mac to do a scan with the questionable machine booted into target disk mode.

My actual scanning procedure was

0) (done before using target disk mode) update system and apps on both machines to current versions

1) compare files on both machines using this script:

DIRS=(Applications Library mach_kernel bin "private/etc" sbin usr);
# leaving out /opt as it seems to just contain MacPorts stuff

for dir in "${DIRS[@]}"; do
  # diff: recursive, just output whether files differ
  diff -r -q --speed-large-files "$1/$dir" "$2/$dir";
done;


1.1) I used a high-powered text editor (vim) to make sense of the output.  My basic strategy was to just organize the lines of output by the first couple of levels of the directory structure using indent-based code folding.  This technique does require some general and POSIX-ish-specific computing knowledge, in particular to differentiate "okay" differences from potentially dangerous differences.

2) I ran chkrootkit using the command

sudo ./chkrootkit -q -r /Volumes/system/


2.1) chkrootkit came up with the following output.  These indications seem to be due to running the scan on a target disk and/or due to differences between the various operating systems that chkrootkit supports.

error: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/strings: can't map file: /Volumes/system/ (Invalid argument)
error: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/strings: can't map file: /Volumes/system/ (Invalid argument)
not tested
not tested
unable to open wtmp-file /Volumes/system/wtmp
not tested: not found wtmp and/or lastlog file


2.2) In order to get chkrootkit to compile, I had to uncomment a line in the Makefile.  It's clearly indicated in the Makefile.  See here for more info.

SUMMARY

I feel pretty confident that this was an effective scan (given the clean state of the scanning system).  However, there are a few downsides to this method:


It assumes that the scanning computer is clean
It requires another Mac (obviously)
It can be painfully difficult to find a 9-pin-to-9-pin Firewire cable


In case you don't have an extra Mac available, here are a couple of alternatives to this approach:


It's possible to put a clean install of OSX onto a USB drive.  To do this, you boot the machine while holding down command-option-R to do an Internet Recovery.  This bypasses the disk contents and uses firmware code to install OSX from Apple's servers.  Apparently you can just plug a USB drive in and choose this as the installation target; afterwards you can boot the machine from the USB drive and run scans on the system drive.  Downside here is that this is a >5GB download, so you'd better have a fast Internet connection (or some patience).
I could have also pulled the drive out of the machine and put it into a hard drive enclosure.  The advantages here are that I wouldn't have had to use a Mac to scan it, and that I wouldn't have had to find a 9-pin-to-9-pin Firewire cable.  Of course, if I didn't use a Mac to scan it, I wouldn't have been able to use my first scanning method (the diff).