How to know which protobuf message the byte array is?

Protocol buffers are not self-describing, so in general when you get a serialized protobuf there is no way to interpret its contents without knowing what schema to expect.

In your case I would recommend using a oneof field. You can have a single top-level message type for your queue messages and let that contain a oneof field that contains either a Person or an Address:

message TopLevelMessage {
  oneof inner_message {
    Person person = 1;
    Address address = 2;
  }
}

The consuming code would then need a switch statement like this in order to retrieve the inner-message:

TopLevelMessage topLevelMessage = TopLevelMessage.parseFrom(...);

switch (topLevelMessage.getInnerMessageCase()) 
{
  case PERSON:
    Person person = topLevelMessage.getPerson();
    ...
    break;

  case ADDRESS:
    Address address = topLevelMessage.getAddress();
    ...
    break;

  default:
     ... 
}

Protobuf 3 introduced the concept of Any that can act in a similar way to the top-level-message pattern explained by @AdamCozzette.

On the write-side you pack your message in an Any:

Person person = ...
Any any = Any.pack(person);

out.write(any.toByteArray());

Then on the read-side you read into an Any and switch on the types you are interested in:

Any any = Any.parseFrom(in);

if (any.is(Person.class)
{
  Person person = any.unpack(Person.class);
  ...
}
else if (any.is(Address.class);
{
  Address address = any.unpack(Address.class);
  ...
}
else
{
  //Handle unknown message
}

Using Any removes the need for special a message type (the top-level-message), but also removes an element of type-safety in as much as you may receive messages that the consuming code does not know how to handle.