どこまでやるかは状況しだいだと思うけど、
使わないプログラムの削除
chkrootkit で定期的にルートキットの検出
ログの定期的チェック
debsums でインストール済みパッケージの検証
/usrをリードオンリーでマウント（あんまり意味はないかも）
/var、/tmpでの実行不許可
bastilleの導入でお手軽に……
tripwire, crack, etc.

WinだとアンチウィルスでOKらしいけど、
Linuxデスクトップ用途ではどこまでで十分なのか

harden-*てubuntuにもある？