Start with these tools:

A - search for rootkits 

chkrootkit:
Checking `ifconfig'... INFECTED
Checking `pstree'... INFECTED
Searching for t0rn's v8 defaults... Possible t0rn v8 \(or variation\) rootkit installed
Searching for Showtee... Warning: Possible Showtee Rootkit installed
Searching for Romanian rootkit...  /usr/include/file.h /usr/include/proc.h
Checking `bindshell'... INFECTED (PORTS:  465)
Checking `lkm'... You have     1 process hidden for ps command
Warning: Possible LKM Trojan installed
Checking `sniffer'... eth0: PF_PACKET(/usr/sbin/iptotal)

rkhunter:
--------------------------------------------------------------------------------
Rootkit Hunter found some bad or unknown hashes. This can be happen due replaced
binaries or updated packages (which give other hashes). Be sure your hashes are
fully updated (rkhunter --update). If you're in doubt about these hashes, contact
the author (fill in the contact form).
--------------------------------------------------------------------------------


   Rootkit 'SHV4'...                                          [ Warning! ]

             --------------------------------------------------------------------------------
             Found parts of this rootkit/trojan by checking the default files and directories
             Please inspect the available files, by running this check with the parameter
             --createlogfile and check the log file (current file: /var/log/rkhunter.log).
             --------------------------------------------------------------------------------

* Application version scan
   - GnuPG 1.2.4                                              [ Vulnerable ]
   - OpenSSL 0.9.7a                                           [ Vulnerable ]
   - PHP 4.3.9-1                                              [ Unknown ]
   - PHP 4.3.9-1                                              [ Unknown ]
   - Procmail MTA 3.22                                        [ OK ]
   - OpenSSH 3.8.1p1                                          [ OK ]

B - more detailed investigation 


#> lsof -i
3         12481   root    3u  IPv4 139597       TCP *:2345 (LISTEN)

# telnet localhost 2345
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
SSH-1.5-2.0.13

#> cat /proc/13066/cmdline
ttyload

# which ttyload
/sbin/ttyload

# ls -l /sbin/ttyload
-rwxr-xr-x   1 122      114        212747 Jul 16 13:37 /sbin/ttyload

# kill 12481
# rm /sbin/ttyload
rm: remove write-protected regular file `/sbin/ttyload'? y
rm: cannot remove `/sbin/ttyload': Operation not permitted

# last
bd       pts/0        pd950ea5a.dip.t- Tue Nov 30 19:05   still logged in
reboot   system boot  2.4.21-pre5-1um  Tue Nov 30 19:04          (00:38)
bd       pts/5        pd950ea5a.dip.t- Tue Nov 30 17:52 - down   (00:46)
bd       pts/0        pd950ea5a.dip.t- Tue Nov 30 17:51 - down   (00:47)
bd       pts/4        pd950ea5a.dip.t- Tue Nov 30 16:52 - down   (01:46)
natraj   pts/2        pd9eb7a77.dip0.t Tue Nov 30 14:38 - 18:00  (03:21)
bd       pts/1        pd950ea5a.dip.t- Tue Nov 30 14:38 - down   (04:00)
bd       pts/0        pd950ea5a.dip.t- Tue Nov 30 14:32 - 17:49  (03:17)
reboot   system boot  2.4.21-pre5-1um  Tue Nov 30 14:31          (04:07)
reboot   system boot  2.4.21-pre5-1um  Tue Nov 30 14:24          (04:14)
joko     pts/2        pd950ea5a.dip.t- Tue Nov 30 14:02 - crash  (00:21)
natraj   pts/0        pd9eb7a77.dip0.t Tue Nov 30 11:28 - crash  (02:56)
natraj   pts/0        pd9eb6304.dip0.t Mon Nov 29 14:51 - 17:57  (03:06)
bd       pts/1        p54802510.dip.t- Mon Nov 29 09:59 - 13:49  (03:50)
bd       pts/0        p54802510.dip.t- Mon Nov 29 08:16 - 10:25  (02:09)
reboot   system boot  2.4.21-pre5-1um  Mon Nov 29 08:10         (1+10:28)

wtmp begins Sun Nov 28 06:37:56 2004

C - more trails 

# nano /root/.bash_history
export TERM=vt100
vi /etc/passwd
passswd bin
passwd bin

# find / -uid 122
/usr/bin/md5sum
/usr/bin/find
/usr/bin/top
/usr/bin/pstree
/usr/sbin/lsof
/bin/ls
/bin/ps
/bin/netstat
find: /proc/25248/fd/4: No such file or directory
/sbin/ifconfig

# cat /proc/25248/cmdline


xukay:/home/uml/quepasa/rootfs/mnt# find . -uid 122
./usr/bin/md5sum
./usr/bin/find
./usr/bin/top
./usr/bin/pstree
./usr/lib/libsh/.bashrc
./usr/lib/libsh/.sniff/shsniff
./usr/lib/libsh/.sniff/shp
./usr/lib/libsh/shsb
./usr/lib/libsh/hide
./usr/sbin/lsof
./bin/ls
./bin/ps
./bin/netstat
./lib/libsh.so/shhk
./lib/libsh.so/shhk.pub
./lib/libsh.so/shrs
./sbin/ifconfig
./sbin/ttyload
./sbin/ttymon


# find / -gid 114
/usr/bin/du
/usr/bin/oldps
/usr/bin/whereis
/usr/include/flio.h
/usr/lib/libsh/.bashrc
/usr/lib/libsh/.sniff/shsniff
/usr/lib/libsh/.sniff/shp
/usr/lib/libsh/shsb
/usr/lib/libsh/hide
/lib/libsh.so/shdcf
/lib/libsh.so/shhk
/lib/libsh.so/shhk.pub
/lib/libsh.so/shrs
find: /proc/1014/fd/4: No such file or directory

D - remove it! 

# chattr -sia /usr/lib/libsh
# rm -r /usr/lib/libsh/

# chattr -sia /lib/libsh.so
# rm -r /lib/libsh.so

[...]

E - refresh system

find @ http://packages.debian.org/ 

# apt-get install findutils 

ls:
# apt-get install fileutils coreutils
# cd /var/cache/apt/archives/
root@quepasa:/var/cache/apt/archives# dpkg -i coreutils_5.2.1-2_i386.deb

ps:
# apt-get install procps

lsof:
# apt-get install lsof

md5sum:
# apt-get install dpkg

pstree:
# apt-get install psmisc

ifconfig/netstat:
# apt-get install net-tools


# apt-get install netkit-inetd
# apt-get install textutils
# apt-get install shellutils
# apt-get install qpopper
# apt-get install vsftpd
# apt-get install rsync
# apt-get install uw-imapd-ssl
# apt-get install libssl0.9.7
# apt-get install ssh
# apt-get install cron
# apt-get install inn
# apt-get install util-linux

F - Todo

G - Infos