There is a special major mode for editing binary files: Hexl mode. To use it, use M-x hexl-find-file instead of C-x C-f to visit the file. This command converts the file's contents to hexadecimal and lets you edit the translation. When you save the file, it is converted automatically back to binary.
You can also use M-x hexl-mode to translate an existing buffer into hex. This is useful if you visit a file normally and then discover it is a binary file.
Ordinary text characters overwrite in Hexl mode. This is to reduce the risk of accidentally spoiling the alignment of data in the file. There are special commands for insertion. Here is a list of the commands of Hexl mode:
Insert a byte with a code typed in decimal.
Insert a byte with a code typed in octal.
Insert a byte with a code typed in hex.
Move to the beginning of a 1k-byte "page."
Move to the end of a 1k-byte "page."
Move to an address specified in hex.
Move to an address specified in decimal.
Leave Hexl mode, going back to the major mode this buffer had before you invoked hexl-mode.
Other Hexl commands let you insert strings (sequences) of binary bytes, move by short's or int's, etc.; type C-h a hexl- RET for details.