It appears that this process has been streamlined a bit. If you right-click in a search field on any site, the context menu has an option to "Add a keyword for this search." The new bookmark will then be created with the "%s" string in the appropriate position in the URL to make this work.

I've set it up for a number of sites since converting over to Firefox yesterday and have yet to find a site that this method doesn't work for.