You can, but if the device is not another 10.5 Mac, it's kind of messy. Apple was careful to qualify in the "300+ new features" marketing that you can search any "shared Mac" on your network with Spotlight (
http://www.apple.com/macosx/features/300.html#spotlight), not any "shared disk".
Anyway, you can force Spotlight to index any mounted disk by using the mdutil utility from the command line. Something like this:
sudo mdutil -i on /Volume/network_volume
There might be some weirdness with unmounting and remounting the network drive, wrt how up to date the index is kept. You'll have to play around with this. Also, the Spotlight GUI is notoriously bad at not providing complete search results. In your testing, I'd recommend using the command line utility "mdfind", which doesn't seem to have the same problems as the GUI.
Note that you can also search any network drive via the Finder, however that does not utilize any index -- the search is basically just doing a complete directory tree walk...