They work like normal shortcuts, just long-press the icon and drop it into the recycling bin, and then open the app menu, long-press Search and drag it down to the dock.
Edit: The dock in question is not customizable from the default settings, but it can be patched through ClockworkMod. The most comprehensive customization options I've seen can be found here.
The files need to be applied through ClockworkMod so the device has to be rooted. Just download the file you prefer, move it to the internal sdcard and apply the update from recovery. Be sure to backup first, just in case.