Debian-based distro

First update your system cache:

apt-get update

Then you can use one of the following ways to search available packages:

apt-cache search <package-name>

There is only package names and simple descriptions.

aptitude search <package-name>

The command provide more information than above one. The first character of the output indicate the package status on your host machine: "i" means installed, "p" otherwise. If the third character is "A" other than space, it means the package is auto installed.

Use "aptitude why " to get the explanation of why the package should be installed on the system.

RPM-based distro

yum list <package-name>