Query bytea column using prefix
For searching by prefix, you just do it.  The hard part (at least from the command line) is getting the binary data to be queried into query in a properly escaped way.

To query a table of file-blobs for files with the ELF header:

select....where data like (E'\\x7f')::bytea||'ELF%'


For indexing it, the main problem you will have is that PostgreSQL btree indexes can't index values longer than 1/3 of the page size (2712 bytes, usually) and a column of binary data is likely to have some records that exceed that.  You can build a functional index on only the first so many bytes of the data, and query that.

create index on thing (substring(data,0,100));


And you can then query it like this:

 select....where substring(data,0,100) like (E'\\x7f')::bytea||'ELF%';


PostgreSQL is not smart enough to realize that for a prefix to match the full column, it most also match a longer-than-the-query prefix of the column.  So that means you must write the match against the expression used to build the index, not against the column itself, or the index won't be used.