Since scripts that are run as part of a policy will run as root you can remove the "sudo" part of the command. If this is a script that you want to be able to track deployment and report on you will want to build it as some sort of package.
You can do all of this with composer. Though there are plenty of other ways to do this.
1. Open Composer
2. Create a new package. - I like to do this by dragging a tiny file that I create. I put stuff in "/private/var/opt"
3. Expand the package using the arrow on the left.
4. Expand the "Scripts folder" using the arrow on the left.
5. Right-click on the "Scripts" Folder
6. Select "Add Shell Script"
7. Select a script type. - I'd choose preinstall
8. Select your script
9. Clear the contents of the script. (except the first line #! /bin/bash)
10. Add your command(s)
Should look like:
#!/bin/sh
networksetup -setsearchdomains Wi-Fi legacydomain.com secondlegacydomain.com additionaldomain.org evenmoresearchdomain.net
11. Click back on your package
12. Build as PKG
Deploy as you normally would...
If it's just a one line command, why not use the "Run Command" field under the "Advanced" section of a policy?
I'm with bentoms; that field in the policy is great for one-liners. You wouldn't need to sudo, however - these commands run in the root context (same with scripts used by Casper).
A little late to the party here, and the execute command section is now found under "files and processes" on the policy, but this little nugget of information helped me a ton today, and will be invaluable going forward.
Very late to the party... But here is my two cents worth.
I try to avoid the Run Command unless absolutely necessary. This is because a Policy runs in a set order (when you edit a policy look under the Optionsl Tab the order starts at the top), the "run Command" executes last in a policy.
I would copy JRM's script and go to management settings, click on Computer Management and Scripts, create a script and past JRM's code here. Once saved you can call it in multiple policies rather than limiting it to one. It also allows you to have an easy way to see your scripts.
Then we simply modify the policy to use your newly saved script. This is particularly useful if you execute a script that will alter a smart group, once "Update Inventory" is run.
As with everything in the Casper suite there is no right or wrong way to complete a task, and everyone's answer so far will work seamlessly. 
