Firefox has a wizard which tells you how to change it the first time you click in the box. If that isn't a good experience for the search box I don't know what is. They have actually significantly enhanced the UX for how searching works when they switched to Yahoo default on installation. (These enhancements may only be in the nightlies right now)
