The only evidence of the existence (or non-existence) of the Brotherhood comes directly from the Party itself. As such, its existence (or non-existence) may simply be part of the mystique of Big Brother and the party apparatus.
Winston is told about the Brotherhood on a daily basis.
A day never passed when spies and saboteurs acting under his directions were not unmasked by the Thought Police. He was the commander of a vast shadowy army, an underground network of conspirators dedicated to the overthrow of the State. The Brotherhood, its name was supposed to be.
Whereas Julia is entirely unaware of the Brotherhood's supposed existence, implying that that knowledge of the Brotherhood-mythos is restricted to lower echelon Party members.
He noticed that she never used Newspeak words except the ones that had passed into
everyday use. She had never heard of the Brotherhood, and refused to believe in its existence. Any kind of organized revolt against the Party, which was bound to be a failure, struck her as stupid.
With that in mind, since the Brotherhood is used as a tool to entrap would-be rebels like Winston (just like the fake bric-a-brac shop) it seems more likely than not that the Brotherhood doesn't exist or else the risk would be that by promoting it, the Party could inadvertently strengthen resistance to Big Brother.
That all being said, we shall let O'Brien have the final word.
‘Does the Brotherhood exist?’
‘That, Winston, you will never know. If we choose to set
you free when we have finished with you, and if you live to
be ninety years old, still you will never learn whether the
answer to that question is Yes or No. As long as you live it
will be an unsolved riddle in your mind.’
And that goes for you too, dear reader.