Google Related Links
Google explains the offering on the Google Related Links page:
Google Related Links use the power of Google to automatically bring fresh, dynamic and interesting content links to any website. Webmasters can place these units on their site to provide visitors with links to useful information related to the site¡¯s content, including relevant news, searches, and pages.
via:http://www.google.com/relatedlinks/faq.html
Are Related Links available to just AdSense publishers?No, we believe that this product is useful for anyone who has a website. You do not have to be an AdSense publisher to use Related Links.
Why does my Google Related Links unit display a search box?
Your Related Links unit will display a search box if you're viewing your page for the first time, or if your site is password-protected or doesn't currently comply with our quality guidelines.
To see whether Google crawlers can access your site, please check your robots.txt settings.
On Research Buzz Tara Calishain comments that at first glance Google Related Links reminded her of the more subdued Yahoo Publisher Network Y!Q product.