First, you can't trust a compromised computer as the output of all utilities could be faked to hide the presence of malicious activities.
I would generally not expect any computer with robust security practices to be part of a bot net. One where you only install code from trusted sources, have strong passwords (that aren't used elsewhere), etc. Unless my ISP says they've received reports of unusual activity from my IP address indicating a potential bot, or a user tells me they were tricked into installing software that didn't do as advertised and they now realize was likely a trojan.
In those cases, I would start testing for signs of a potential bot:
monitor network activity. Run netstat -- do all connections more or less make sense? (ignore local connections; run whois on foreign IPs I don't recognize). Remember netstat's output could be faked, so you also run wireshark (network analyzer) from another computer (presumed safe) on my local network, and check to see if there's any unusual traffic to/from strange non-local IP addresses (that's not routine stuff from my router/network printer, etc)?
Boot into a live cd of the same distribution (so you trust the utilities), and run checksums (md5) on important utilities (/bin, /sbin/, /usr/bin/, etc.) and compare to known checksums of a safe computer with the same OS / version (or make a fresh install and run all updates and then generate checksums to compare with). (If the checksums don't match, it could possibly be due to an update of the utility; so check versions and investigate further). I've assumed linux/unix system for this answer, but presumably you could do the same for windows if you know what to check.
If you find evidence of a bot, I'd back up my data (that is non-executables), wipe the hard disk clean, and re-install the OS from a safe source with different passwords. I'd be very wary opening up documents that could contain macros (e.g., doc, pdfs) from the compromised computer (making sure to disable macros in the relevant programs before looking at these files again, not being logged in as administrator/root, and installing a virus scanner).