I'm not quite sure I follow John@Home's arithmetic, but it seems hard to beat something in the range £30 to £33 each unless you take up his suggestion of a Two Together Railcard. [EDIT: his arithmetic's fine, it's just that his second £12.90 should be £21.10].
If you are happy to buy advance tickets, Newcastle-Leeds and Leeds-Newcastle Advances (avoiding very early in the morning) would start from a total of £66, and you might save a few pounds by splitting Advance tickets at Northallerton.
For non-Advances, trainscanbecheaper suggests day returns splitting at Hartlepool and Church Fenton for a total of about £60, but presumably an unacceptably long journey.