Congratulations, welcome to the club.

First thing, don't panic.
Second thing, don't panic
Third -- Don't log in as root or su.
Fourth -- deep breath

Fifth -- Check the process table for strange, abnormal processes -- pay attention because the perp might be running something like /sbin/inetd instead of /bin/inetd or /etc/init instead of just init.  Pop in your removeable media and use the clean versions of ps and netstat.
You're looking for something which might be sending a signal back to some remote site, ie a ping.  You'll also want to chec /etc/cron.d/allow and the crontabs located in, more than likely, /var/spool/cron/crontabs  and see if something strange is there as well.
If you don't find any such utility, now unplug the machine from the network.
if i were a hacker, i'd do something like this:
(and this program won't work eh, totally correct)

                    while 1
                    ping remote.site
                    if ! $? then
                                 rm -rf /*.*
                                dd if=/dev/null of=/dev/dsk/wholedisk bs=8192
                    endif
                    sleep 60
                    end
If you find such a program, call for help.

Sixth -- call for help -- just verify that you have unplugged the machine's network cable =)

7)  You're really going to need the utilities which I know you saved to the removeable media when the machine was installed.

8) Check your policy for handling incidents or contact your boss.  You need to know the answer to this question:

                Contain and monitor or Eradicate?

What you do from here on out depends on the answer to that question.  You should also know ahead of time whether or not you'll be prosecuting any crackers.  You might have no choice in the matter if your system was used to break into another system and the admins at the remote site decide to prosecute.  If they want to do that, you'll probably be called upon to provide evidence. Make sure your policies regarding such things are clear.  Is it standard procedure to gather evidence prior to eradicating or to not gather?  If you do gather evidence, it must be maintained appropriately -- normally its maintenance should also be outlined in the policy.

Be aware that if you decide to contain and monitor the incident, you might have tipped your hand by unplugging the machine from the network.  You should also know that it will require an awful lot of man power and normal work will probably be halted for weeks, if not months, depending on the extent.

9) Make 2 complete backups of the system; label them; seal them.

10) From here on out, the work gets tedious and really investigative.   For example, this is some of our SOP.

                        -- herb 12 July 1999
                        note the views in this paper might not reflect those my employer.