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.
Best Answer
About 2 years ago one of my co-located web servers was hacked. I tracked down the vulnerability to be in a php script I was running, an old version of PHPBB. The hacker basically used a hole to place a script on my server and execute it, which gave him full access to the server.
Luckily, he didn't do any damage, he simply installed a new website to be served off my box.
I was going through the logs one day, as I had seen my bandwidth usage skyrocket, and I found that he had installed a spoofed copy of another website on my server. Essentially it was an easy misspelling of an online store for watches, and I believe he was selling watches, collecting money, and obviously never sending anyone anything.
After I discovered this, I made a copy of everything he did - logs, scripts, the entire website, and archived it as well as sent it to my hosting provider.
I cleaned up his tracks, and began to secure my server.
As a result, I learned a lot about Linux security, and did several things:
As a result, I have not been hacked since, and whenever anyone tries, I am alerted.
Some of the easiest ways your server can be hacked, if it is a standard web/email server are through common script vulnerabilities. You also should take extra steps if you are running an email server to ensure you are not an open relay of any kind, the spammers will find you and suddenly all email coming from your server will get blacklisted.