This feature has been sponsored by the New York State Senate. The issue spec is on the issue tracker.

I am very glad to have opportunity to work on this feature and sharing my thoughts and experience for same :) . This feature is added in trunk and scheduled for version 4.2 release

When User wants to perform a common task (eg: add contacts to group) on multiple contact, user searches contacts through Find Contacts or Advanced Search, and in the case result spans upon multiple pages, user selects desired records which reside on different search result pages and performs task each time after per page records selection. This is really troublesome to user, to perform a common task mutiple times after per page records selection.

Quite a few changes were made in this feature . Civicrm already had caching technique implemented, this technique is extended to remember the selected contacts while traversing across pages as well as fetching the selected contacts while performing action task. The caching functionality which is the heart of this feature was extended and used. Existing prevnext_cache table and the newly introduced is_selected column are used to maintain selection during pagination(alphabetic as well as numeric).Everytime contacts are selected, AJAX calls are made to store the selection .Usage of is_selected column are extension to this caching functionality. Large amount of query time was reduced, which was comming up during traversing the search pages, by preventing unwanted database communication. Optimization in the action task functionality is done by preventing a search query fire again and firing a lighter query to use the cache table to fetch the selected contacts on any action task page.
 
End-user will benefit this feature. Previously user had to traverse across multiple pages by using alphabetic or numeric pagination, select contacts , and preform a common action task per page selection. Now user can really use alphabetic or numeric pagination for multiple contact selection when the desired contacts spans across multiple pages. This feature will remember the selections done by the user on each page, so that after the user finishes selection of records which spans multiple pages, user can perform a common task . This feature also provides user the facility to reset all selections made, and also user can traverse through search pages to confirm selections before performing the action task. Also when the search yields large number of contacts ,the optimization done to task functionality and caching functionality will benefit the user greatly in performance.