First - let me clear up a possible misconception.
When you talk to another website, you're generally going to have to use whatever interface they've supplied; you can't query their database directly. As an example, Yahoo! stores their data using a complex proprietary system, but you simply use http://search.yahoo.com/search?p=cats to search for cats. You don't (and can't) query their database. (This is for both reasons of security and complexity - letting an arbitrary person run queries against your database means you have to manage access and prevent DROP TABLES from happening - and to allow the database to be changed around without you having to care what it is or how it works.)
You can probably do what you want to do, but you'll need to go to each site's search function and see how it's done, as in, what URL the search form lives at and what data needs to be supplied to do a search; you may find WWW::Mechanize very helpful, as it acts like a browser that you control via Perl. You can fill out a form and submit it, get the resulting HTML back, and then parse out the search results.
