Remove or disable unneeded services, particularly network services. For example, if you don't need a web-server, ftp server or Samba server, don't have them running.
Consider finding more secure server applications, where possible. (e.g., use VSFTPd rather than WU-FTPd, which is commonly installed on many Unix/Linux systems; or replacing sendmail with a simpler, more secure SMTP server).
Configure the firewall software. Virtually all Unix/Linux variants have built-in packet filtering firewalls.
Linux (kernel 2.4 and above) - Netfilter/IPTables - There are various configuration tools available (most distributions include at least one) if you aren't comfortable configuring using the command-line interface.