Does Spotlight search work with a Time Capsule?
Yes.
Per default, it will be indexed. You can opt-out any location in...

System Preferences → Spotlight → Privacy

If you add and remove a location in the privacy tab, it will be re-indexed.
Also see Apple's support document Spotlight: How to re-index folders or volumes.