Is SSH available to the outside world? Many many compromised hosts spend all their time trying to login to remote hosts with dictionaries of usernames/passwords to try.

If your (root) password is weak then I'd not be surprised if that was the source of the infection.

You might see logins via "last", or via the system logs.