Look first in the Linux Software Map. It's at: ftp://ibiblio.org/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 Projects 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. See (See: "How To Port XXX to Linux.") If it's a large package that may require some porting, post a message to comp.os.linux.development.apps.
If you compile a large-ish program, please upload it to one or more of the FTP sites, and post a message to comp.os.linux.announce (submit your posting to email@example.com).
If you're looking for an application program, the chances are that someone has already written a free version. The comp.sources.wanted FAQ has instructions for finding the source code.