The Web is enormous and in constant flux, causing much content to be lost over time. Historical collections of web content are thus of monumental value in preserving records of significant aspects of modern society. The Internet Archive offers access to hundreds of billions of historical web page snapshots. The scale of such archives, however, presents tremendous challenges to making this content fully searchable. This research effort investigates efficient and effective approaches to store, index, and retrieve web content from large-scale historical archives. In addition, the temporal content and structure of the archives are mined to exploit temporal characteristics that can improve search result ranking. Technological advances from this work are being tested on content from and in collaboration with the Internet Archive and integrated into its infrastructure, enabling new archival search capabilities for the public.