Provided that the ARD client is installed on the workstations, you would use the "networksetup" command to set this property. On 10.5 and greater, I believe that the client is automatically installed and on 10.2-10.4 you may neet to install it to get the full functionality.
networksetup also has two paths, depending on whether the client came with the OS or had to be installed:
/usr/sbin/networksetup
/System/Library/CoreServices/RemoteManagement/ARDAgent.app/Contents/Support/networksetup
The flag you want is "-setsearchdomains" with two arguments--the network device to be set, followed by the search domains.
So, a script that would basically work in all cases for you would be:
#!/bin/sh
/System/Library/CoreServices/RemoteManagement/ARDAgent.app/Contents/Support/networksetup -setsearchdomains AirPort ourcompany.com example.com
/System/Library/CoreServices/RemoteManagement/ARDAgent.app/Contents/Support/networksetup -setsearchdomains "Built-in Ethernet" ourcompany.com example.com
/System/Library/CoreServices/RemoteManagement/ARDAgent.app/Contents/Support/networksetup -setsearchdomains Ethernet ourcompany.com example.com
/usr/sbin/networksetupnetworksetup -setsearchdomains AirPort ourcompany.com example.com
/usr/sbin/networksetupnetworksetup -setsearchdomains "Built-in Ethernet" ourcompany.com example.com
/usr/sbin/networksetupnetworksetup -setsearchdomains Ethernet ourcompany.com example.com
exit 0
You can push these command one-by-one via ARD or create a no-payload package via packagemaker or iceberg to push it out as a package via ARD (I would do the latter). The script should change all network devices on any OS X machine to have your preferred search path BUT it will only be set for the current network profile. To change other network profiles, you will have to make another profile active first.
Does that help?