The google blog recently put up a remarkably content-free post on their product blog about how they use iterative design and usability studies to develop enhancements to their core search offering.
We do similar testing for our search product (http://search.comcast.net) and we actually run 8-12 live tests at any given time. The real users using the product in the wild give us fantastic insight that is combined with the more traditional studies in order to guide us.
I’m embarking on a similar approach for our new CMS initiative and I’m still on iteration 0.
I don’t have pretty design concepts to show yet, but I do have cartoon wall art!