I've noticed a message on the upper right hand corner on the search results page saying "Personalized based on your web history"

http://img182.imageshack.us/img182/5976/screenshot3oa1.png

[URL updated – Tony]

I think it appears when I search for certain words. It shows up only when I search for popular words like music, movies, etc...

Yep. They've been doing that since the end of July:

http://googleblog.blogspot.com/2008/07/more-transparency-in-customized-search.html