1. Go through the system and application logs, check for any anomalies,
2. Check your authentication (passwd,group) files for accounts added you didn't,
3. Check network interfaces and connections and running processes for ones you can't remember running and inspect,
4. Try to verify your systems integrity by comparing checksums with those from rpm's on read-only media or a remote ftp.
5. Compile chkrootkit on a box you trust and run it on the server.
I. Please use the Linux - Security forum for security incidents and questions
II. For a general checklist see Intruder Detection Checklist (CERT)
III. Also check out the LQ FAQ: Security references