I would do it as follows:
(1) Place a checkbox in a prominent place on the page (indicating that it is a multiple selection);
(2) Make the click on the checkbox activate a javascript where:
(a) all visible checkbox elements of the page are selected (to give the full selection effect);
(b) make a selection of all criteria elements (regardless of whether they are listed or not on the page). In my applications, I like to display the total number of selected items next to the selector, this gives further confirmation to the user that he has selected all items and not just those on the page.
(3) Perform your operation.
What the GMAIL does is identical to the above. When performing a filter it does the following procedure: 1º executes the query and saves the result, 2º shows a number x of results, 3º when selecting all it marks the x results on the screen (for presentation purposes only) and 4th executes the action on all the result of the saved query in the first step.
Good luck!