Rewriting @mschonaker's answer to be a little more clear.
Both users need to subscribe to each other and accept the subscription request they received. Let's call them Alice and Bob. Alice sends a subscription request to Bob:
Presence subscribe = new Presence(Presence.Type.subscribe);
subscribe.setTo('[email protected]');
connection.sendPacket(subscribe);
When Bob receives the request, he approves it:
Presence subscribed = new Presence(Presence.Type.subscribed);
subscribed.setTo('[email protected]');
connection.sendPacket(subscribed);
Bob may also be interested in Alice's presence, so he subscribes to her:
Presence subscribe = new Presence(Presence.Type.subscribe);
subscribe.setTo('[email protected]');
connection.sendPacket(subscribe);
And Alice needs to approve Bob's request:
Presence subscribed = new Presence(Presence.Type.subscribed);
subscribed.setTo('[email protected]');
connection.sendPacket(subscribed);
Section 3.1 of RFC6121 is the current best reference for how this works.