design question about "programming to interfaces"

I have a design problem that I am unsure of how to deal with, the
problem is as follows.

The basics:

I am creating a search dao for using google, the dao should support
several search types: pages, news, images and perhaps more. These
queries are similar in the mechanics as leveraged by the interfaces, but
the details are different, specifically the handling and passing of the
arguments and the result data throught the interfaces. Specifically, how
to specify the query string is the same for all, but the contents are
different because of the nature of each searchtype. The same goes for
the result. So, the question is how do I pass differing query arguments
and result data in a design based on "programming to interfaces".

The details:

Example: In addition to a common query string such as "car", "engine"
etc I can specify, for images: gif, jpg etc. colour/bw,
thumbnail/original etc. for news: the newsgroup, sender, threaded etc.
All of these special query parameters have their own parameter names.
The same goes for the result, the basic format is the same xml, but much
of the elements and attributes are specialised.

The mechanics of the search are the same; some parameterized query
arguments, the correct search engine and a mathcing result parser. All
which can be handled by interfaces and delegation.

The design problem I am having is how to deal with the query parameters
and the result data when programming to interfaces. I have allways been
told that one should expose the data in objects. Meaning, data to be
passed in an object should be given a member variable for each data
element with a corresponding get/set method. If I were to do that for
the search parameters and the resultlist I would need a new interface,
and implementation, for each new type of search I was doing. This would
result in massive dupliction of code. I could potentially create a super
object, or a marker interface, and use that as the datatype for the
search argument and resultlist type, but then I would have to insert
lots of casting and that would defeat the purpose of interfaces.

Any thoughts on how to do this properly?

regards

tom