Newspaper is made out of cellulose fibres (linear unbranched ones) bonded entangled together.
The fibre structure is anisotropic. The orientation of most of the fibres is along the direction of the movement of the machine.
In the direction of this orientation, it is relatively easier to tear a newspaper because it's just a matter of prying two fibres apart. (without significant tearing of fibres)
In the direction perpendicular to this, fibres have to be broken to tear the paper, and this requires a greater force.
The same asymmetry account for why tears are neat/messy depending on the direction you take.
If a piece of paper was isotropic, with random orientation of fibres, tearing would roughly take the same effort in any direction.