If you have reason to believe that the system may be compromised then wipe the server and restore from last known good backup.
By all means take an image to see if you can determine how the system was compromised and plug the vulnerability. But this is not an easy process, particularly if you have no experience at this kind of thing - indeed if you attempt this yourself then it's likely that such intervention may occlude the nature of the compromise - certainly the "evidence" would be considered severely tainted by any law enforcement / jurisdiction.
Validating the package checksums is a starting point — but not nearly as effective as a properly managed file integrity checking regime (tripwire, LIDS etc). Logs are good place to look too. But you have to understand what these tools are telling you.
There's lots of things you should be doing before a system is compromised: configuring the permissions, firewall, optionally installing additional security measures such as mod_security, suhosin, fail2ban etc. Part of the maintenance of a server should be running a rootkit detector on it regularly. For a system/cluster of significant value you should also be carrying out periodic vulnerability scanning. But there's no point in doing any of this after the event.