This is a ComboBox:

This is a FilteringSelect:

This ComboBox uses a customized QueryReadStore, it prepares the query-string for the URL that way that the paging parameters "start" and "count" are also send.
Click here to see the code!
The HTML might look like this, the important attribute: doClientPaging="false" this takes care that the same query is fired to the server and its not assumed that the client (the store) does the paging on the old data.

    <div dojoType="ServerPagingReadStore" jsId="serverPagingStore" url="stores/QueryReadStore.php" requestMethod="get" doClientPaging="false"></div>
    <input dojoType="dijit.form.ComboBox" store="serverPagingStore" pageSize="10" />

    		dojo.require("dojox.data.QueryReadStore");
    		dojo.provide("ServerPagingReadStore");
    		dojo.declare("ServerPagingReadStore", dojox.data.QueryReadStore, {
    			fetch:function(request) {
    				request.serverQuery = {q:request.query.name, start:request.start, count:request.count};
    				return this.inherited("fetch", arguments);
    			}
    		});

requestMethod get post
queryOptions
ignoreCase
true false
deep
true false
paging start: count:
do client paging: