I'd first block the connection to the external addresses using the iptables
iptables -A OUTPUT -d IP_Address -j DROP
Once you've made sure all the IP Addresses are being blocked, save the iptables: # /sbin/service iptables save
then clean up the files placed by the hijacker.
You may want to look at /etc/var/log/messages
and /etc/var/log/secure
to see if there are any entries left by the hijacker that may indicate how he/she may have grabbed a foothold on your server.
If you are running a website, make sure you don't have any web pages that allow users to upload files like PHP shells.
This should get you started. You can also ask your hosting provider to perform an antivirus scan to look for any scripts / files that allow access.