Yesterday, I was conducting a search on michael jordan for this post and I spotted related searches at the bottom of the Google results. It looked like this:

I thought it was new, but waited on it. I then saw a post at WebmasterWorld this morning by senior member, crobb305, who believes it is new as well. If it is not new, it is for sure showing up for more and more search results.
Forum discussion at WebmasterWorld.

Comments:
Michael
12/19/2006 03:35 pm
I noticed that too. It didn't stick out and was an accident that I even noticed it. My thoughts are that most people will not even notice this unless it gets moved to the top of the page.
Matt Cutts
12/19/2006 06:32 pm
This is new. We do lots of different tests to see how and whether they help users.
Farooq
12/20/2006 03:55 am
I've been seeing it mostly on medical terms for about two weeks now.