For the benefit of those, like me, who encounter this problem with a recent install, note that the solution has changed since the transition in Testing to KDE Frameworks 5: don't install baloo4, it won't work with current dolphin. Instead, install baloo-kf5.
Maintainers, please consider making plasma-desktop (or some package you think is more appropriate - perhaps dolphin) at least recommend baloo-kf5. From what I can tell, right now, nothing even suggests baloo-kf5, and it's rather opaque to an ordinary user that this package might be necessary for some standard functionality. Peace, Brendon