Well, first figure out where you are going to start selling. Then, search with the site search [searchengineworld.com] to find stuff about the search engines in that country. :) We've got a lot of info here, and I don't have any links handy to that info.
Aside from that I would say these are the majors:
Inktomi, Teoma, FAST / Alltheweb, and Altavista, but really, those last 2 are the same since Overture bought them.
Many of those have international reach, and of course, Google is free. Then there are directories, and pay per click.