Your case is special. If you were to say two people were "sitting on a tree" in this case, it would imply that the tree was on the ground—i.e., that it had fallen or been cut down. Sitting "in" a tree means sitting in among the branches, most likely at least partly hidden from view.
I wrote the above eight years ago, and still stand by what I say. Nevertheless, there are nuances to everything. Consider first this stanza from W. B. Yeats's "Sailing to Byzantium":
That is no country for old men. The young
In one another's arms, birds in the trees,
—Those dying generations—at their song,
The salmon-falls, the mackerel-crowded seas,
Fish, flesh, or fowl, commend all summer long
Whatever is begotten, born, and dies.
Caught in that sensual music all neglect
Monuments of unageing intellect.
The poet is concerned here to draw a contrast between old and young, and the birds (in the fragment I boldfaced) are on the youth side of that equation. No place, there, for fallen trees; these are youthful, upright and leaf-covered.
Now, the leaves are probably the origin of the use of the preposition in with respect to trees: the birds are in among the leaves. Unless the foliage is sparse, you probably can't even see the birds, though birdsong may announce their presence. They are in among the branches, in among the foliage. Even on a leafless dead or dormant tree, though, we still refer to birds in the trees.
Note, however, that it is entirely proper to say that a bird lights on (or upon) a branch. There it is quite obvious we are close enough to actually see the bird in the tree.
Now, just to confound everyone (and reveal the nuance), consider another reference. This is from The Mikado by Gilbert & Sullivan, from the song "Tit-Willow":
On a tree by a river a little tom-tit
Sang "Willow, titwillow, titwillow"
This is a legitimate usage, one that would seem to contradict my statement about the in usage. But I don't think it does. Gilbert is offering a little sketch of a bird singing, and to do so it must sit on a branch. We're given a close-up of the bird, and the economy of words necessary to lyricize a simple song forces Gilbert to pare down the verbiage, so the ideas are telescoped: "On a branch of a tree" simply wouldn't scan. And had he used in in this case the focus would have been widened to emphasize the tree, not the bird—hardly appropriate to the song of a little bird.
This whole matter just illustrates once again how squishy and difficult prepositions can be in English—or in any language, for that matter.