I'm looking for a program that does X and runs on unix (or at least on my particular unix system). Where can I look? Is there a more efficient way than a generic web search?
The first place to look is your distribution's package list. That's where you'll find the easiest-to-install programs. Some package management tools provide advanced ways of searching it.
On Debian and Debian-based distributions (e.g. Ubuntu), you can search package descriptions with
aptitude search(on the command line), or through the search facility in interactive package managers such as Aptitude and Synaptic. There's also more structured information in the form of tags: install the
debtagspackage, and make basic queries with the
debtagscommand or browse the tag database in Aptitude. Tags are a good way to find packages to work with a particular file format, for example.
On Red Hat and other distributions using yum (e.g. CentOS, Fedora), you can search package descriptions with
yum search(on the command line).
If the package is not in your distribution, it might be available from an unofficial source. Try the Linux packages search, which indexes several official and unofficial sources of Linux packages. For Ubuntu, search for the package in a PPA.
A good place to find software, especially for Unix and Linux, is freshmeat. It is a well established site that lists software projects together with a short description, license information, popularity and vitality stats, information about which programming language is used and much more, searchable by subject.
In addition to the other suggestions forwarded, there is a good site out there called Alternative To that is great for looking up software for other platforms based on some piece of software you know on another platform.
We catalog useful free software that runs under free operating systems — particularly the GNU operating system and its GNU/Linux variants.
Licenses are verified for each and every program listed in this directory.
For each listed piece of software, a short description is provided, together with links to the homepage and user support resources are provided, as well as checkout commands and/or links to where the program sources can be downloaded.
In line with Caleb's answer there is the Linux App Finder. I generally find it easier to start with a Windows app and search for "linux alternative " as Windows apps are usually easier to find information on because they are more heavily promoted and more people know about them.
BerliOS also hosts a good number of UNIX/Linux applications.
In gentoo and derived systems, there are several neat programs to search the portage (which, in short, is gentoo's software database). The one I like most is eix.
The best online search for gentoo is gpo.zugaina.org. It searches not only the default gentoo portage, but also all popular overlays (unofficial/3rd party databases).
A somewhat naive site, but very useful for those coming from Windows, is: