Can I search bash history across all users on a server?

Use getent to enumerate the home directories.

getent passwd |
cut -d : -f 6 |
sed 's:$:/.bash_history:' |
xargs -d '\n' grep -s -H -e "$pattern" 

If your home directories are in a well-known location, it could be as simple as

grep -e "$pattern" /home/*/.bash_history

Of course, if a user uses a different shell or a different value of HISTFILE, this won't tell you much. Nor will this tell you about commands that weren't executed through a shell, or about aliases and functions and now-removed external commands that were in some user directory early in the user's $PATH. If what you want to know is what commands users have run, you need process accounting or some fancier auditing system; see Monitoring activity on my computer., How to check how long a process ran after it finished?.

find /home -name .bash_history | xargs grep <string>

Alternatively:

grep string $(find /home -name .bash_history)

Note that this covers home directories in default locations. It would be better to parse /etc/passwd or invoke getent, and parse the output of that.

for i in $(getent passwd | cut -d: -f6 ); do grep string ${i}/.bash_history; done

You could do

find /home | grep bash_history | xargs grep "whatever"

But I don't really think that is much better then what you were thinking.