1. VMware Tools on Linux systems is not installed automatically
2. Many new linux distros now includes the open source version of VMware Tools known as open-vm-tools.
Distros that are known to include open-vm-tools is: Debian 5.0 (lenny), Ubuntu 8.10, Gentoo, OpenSUSE 11, rPath, SourceMage
On these distros you can install open-vm-tools with the standard package manager (synaptic, emerge, etc). This is the easiest method.
From the command line on debian/ubuntu based distros you can do:
$ sudo aptitude install open-vm-tools
On other Linux distros you will need to install VMware Tools manually. When you click Install VMware Tools... from the menu, VMware will mount a virtual CDROM in the VM containing the tools and nothing more.

If you're using a distro that is not officially supported there might also be additional steps involved when installing the tools this way. This typically happens if your kernel version is newer than the VMware product used on the host. Please consult your distros documentation or community for details.
In order to install VMware Tools you will need to have the linux kernel headers for you running kernel and gcc build environment installed. In debian 4.0 that means: apt-get install autoconf automake binutils cpp gcc linux-headers-$(uname -r) make psmisc
VMware Tools is shipped in two different formats: rpm and tgz

Note that even though none of these say x64 and one of them say i386, both of them are also x64 capable packages. You should only install one of these packages in your linux guest.
You should not use the rpm format on non-rpm based distros (even with alien or similar). Use the tgz instead.
Distros where you should use rpm includes: Redhat Enterprise Linux, Centos, Fedora, Suse, Oracle Enterprise Linux, and others derived from these
To install this package you will need to access the VMs cdrom drive. On some distros it is mounted automatically when you press "Install VMware Tools.." while on others you will need to mount it manually with a command such as mount /dev/cdrom
RPM based distros
If you're using a rpm based distro you can install VMware Tools directly from the mounted media by using a command such as rpm -Uvh /media/cdrom/VMwareTools-x.x.x-xxxxx.rpm
If you have an error message at the console at this point, please see here: VFS: busy inodes on changed media or resized disk hda
To complete the configuration you will have to run vmware-config-tools.pl
Other distros
For other distros you will need to unpack the package first and then run the included installer with commands like this:
cd /tmp
tar xzvf /media/cdrom/VMwareTools-x.x.x-xxxxx.tar.gz
cd vmware-tools-distrib
./vmware-install.pl
The tools will now install and it will ask you a series of questions that you will need to answer. If it keeps asking you about the location of the kernel headers it usually means that the version you have installed doesn't 100% match the version you are currently running. The VMware Tools package is very picky about it and the versions need to match.
When the VMware Tools package is installed you will also get a status about this in the VMware GUI:

If VMware Tools is not an up-to-date version you will instead see the message:

If you already have a fairly recent version of VMware Tools (mid 2006 and newer) you can choose to automatically upgrade the tools:

NB: While this method of upgrading is known to work, some distros will require you to manually restart networking after the upgrade since the VM looses network connectivity during the upgrade.
If you want to reconfigure vmware tools later you can run vmware-config-tools.pl
PS: Many of the steps above can also be done from the GUI on many linux distros.
For CentOS, RHEL, SUSE and Ubuntu you can also find info on official VMware repositories here: http://www.vmware.com/download/packages.html