The companies said that Google's search technology will be used in the search areas of CompuServe, AOL.com and Netscape.
Financial terms for the multiyear agreement between AOL and Google were not disclosed.
The alliance will improve searching capabilities for AOL users by granting them access to Google's Internet search engine technology, while Google will become available to AOL's 34 million members as well as the tens of millions of visitors to AOL's Web-based properties.
Google and AOL also signed a marketing agreement, that allows Google to pitch its targeted paid listings product from its base of advertisers to AOL users.
The deal comes a day after Overture Services, which handles advertising for search engines, said its US search distribution relationship with AOL had ended. AOL users in the US will no longer receive paid listings provided by Overture's advertisers though its entries on AOL Europe's portals in the UK, France and Germany will continue.
Google is closing in on Yahoo! as the world's most popular search engine.