Here are some things to try before rebooting:
First of all, if you think you might be compromised unplug your network cable so the machine can’t do further damage.
Then, if possible refrain from rebooting, as many traces of an intruder can be removed by re-booting.
If you thought ahead, and had remote logging in place, use your remote logs, not the ones on the machine, as it’s all too easy for someone to tamper with the logs on the machine. But if you don’t have remote logs, examine the local ones thoroughly.
Check dmesg, as this will be replaced upon reboot as well.
In linux it is possible to have running programs – even after the running file has been deleted. Check for these with the command file /proc/[0-9]*/exe|grep “(deleted)”. (these disappear on reboot, of course). If you want to save a copy of the running program to disk, use /bin/dd if=/proc/filename/exe of=filename
If you have known good copies of who/ps/ls/netstat, use these tools to examine what is going on on the box. Note that if a rootkit has been installed, these utilities are usually replaced with copies that won’t give accurate information.