They both sound correct, but they have different meanings.
John cheated Mary.
John used some kind of dishonesty in order to take something away from Mary. Example: Mary gave John money to invest for her, but John spent the money on himself.
John cheated on Mary.
This sentence has only one meaning: John has promised Mary that he will not have romantic relations with any other women, but he broke that promise.