It depends, but mainly by witnesses, catching during the act, or acting on mere suspicions
And at some times and cultures oaths and ordeals also came into the game
For example in the 10th century Constantinopolis, the process is described like this in the icelandic saga (see chapter 91 and 92):
The husband tried in wain to catch the wife's lover, and it was in this case the lady who demanded to be allowed to take an oath by a special ceremony before the bishop to prove her innocence. After she made the oath she promptly divorced him, and he was banished at the pressing of her kin for his false charges.
Or among the ancient Jews the standard procedure was to catch in the act or find witnesses, (in which case the wife was to be executed) but if that did not work, there was a special ordeal.
Hammurabi also required that both the wife and the lover shall be bound and thrown into water (covering only the case when they are caught lying together), but maintained that the husband is allowed to save his wife, and the king the lover, if he be his servant.
And in the last 150 years the well-off could also hire private investigators to spy on their spouses, and produce either photographical or indirect evidence.(like records on a secret booking in a hotel)
There are also plenty of examples in literature on the traps and ruses jealous people devised. (like pretending to travel abroad, and coming back unexpectedly)