Here are some of the ways you may come to know that your server security has been compromised.
You received an Intrusion Alert(s)
Your website has been defaced
There has been a dramatic decrease/increase in your disk space on server
You are experiencing high network usage
Other Server Administrators are contacting you.
The output for ifconfig -a displays PROMISC. In promiscuous mode your box will be catching all packets.
You suddenly find that your history file is empty i.e., has been overwritten.
You find truncated/erased log files
You noticed utmp/wtmp files have been tampered
You find new users on your system.
Process investigation reveals strange process names
Your sshd server is owned by someone else.
There has been an unexplained rise in CPU usage
Other accounts on your network have been cracked.
When "Things just don't seem right"
You are loosing ssh connection continously.
If you can think of something else, please comment and I will add it here.