SearchBin is a fast commandline program for searching within binary files. It's a bit like grep for binaries. It offers wildcard matching and has three capabilities for searching: for bytes using hexidecimal, for a plain text string, and for a smaller binary file. Any discovered matches will print the found offsets (0-based).
Binmay is a command line binary search and replace program. It allows one to specify a binary string (in hex) to search for and, optionally, a binary string to replace it with. One can mask both search and replace strings as one can mask an IP. It is handy for changing broken user SID/RIDs in ntuser.dat files after you move a profile from somewhere to somewhere else.