Look first in the Linux Software Map.
It's at: ftp://metalab.unc.edu/pub/Linux/docs/linux-software-map/, and on the other FTP sites. A search engine is available on the World Wide Web at http://www.boutell.com/lsm/. Also check out the Freshmeat Web site: http://www.freshmeat.net, which is where many new announcements of free software first appear.

Freshmeat is basically a site index that continuously updates the notices of new or upgraded software for Linux, and maintains indexes of the announcements and links to their URL's. The FTP sites (Where Are the Linux FTP Archives?) often have ls-lR or INDEX directory listings which you can search using grep or a text editor. The directory listings files can be very large, however, making them unwieldy for quick searches.
Also look at the Linux Project's Map: ftp://ftp.ix.de/pub/ix/Linux/docs/Projects-Map.gz.

There's a search engine for Linux FTP archives at: http://lfw.linuxhq.com. Searching for "Linux" on the World Wide Web provides copious references. (Where Is the Linux Stuff on the World Wide Web?) If you don't find anything, you could download the sources to the program yourself and compile them. 

 

If it's a large package that may require some porting, post a message to news:comp.os.linux.development.apps. The popularity of Linux makes this an extremely unlikely occurrence. The great majority of software available on other Unix-type systems has already been ported to Linux. If you compile a large-ish program, please upload it to one or more of the FTP sites, and post a message to news:comp.os.linux.announce (submit your posting to This e-mail address is being protected from spambots. You need JavaScript enabled to view it . If you're looking for an application program, the chances are that someone has already written a free version. The news:comp.sources.wanted FAQ has instructions for finding the source code.