I have read many different posts about how to enable Spotlight to find archives, etc., on external volumes, but I didn't find a solution to make Spotlight to search on a Samba volume. I found one post on macosxhints, but then I found this one about how to make Terminal tell Spotlight to index external volumes. However, although it says it works on Windows volumes, it did not work for me -- I was able to make Spotlight index the volume, but it didn't search on my Samba external volume.
Today I read a fantastic post titled Using Spotlight from the OS X Command line, so I figured that mixing the two solutions would work ... and it does!
If you first index the Samba volume following the steps in the first link, you can then search using Terminal and the tips in the second link.
[robg adds: I emailed the author to confirm that simply indexing the volume wasn't enough. Spotlight failed from the GUI but worked in Terminal. Many of the tips in the second link have been published here before, but I thought it worth sharing this odd 'combo' solution in the event that it helps others in similar situations.]

