What should a man do if he finds out that his wife isn't a virgin on his wedding night?

Tell his wife's parents. If they can't find the tokens of her virginity, then all the men of the city must stone her to death at the door of her father's house.

If any man take a wife, and go in unto her, and hate her,

And give occasions of speech against her, and bring up an evil name upon her, and say, I took this woman, and when I came to her, I found her not a maid:

Then shall the father of the damsel, and her mother, take and bring forth the tokens of the damsel's virginity unto the elders of the city in the gate:

And the damsel's father shall say unto the elders, I gave my daughter unto this man to wife, and he hateth her;

And, lo, he hath given occasions of speech against her, saying, I found not thy daughter a maid; and yet these are the tokens of my daughter's virginity. And they shall spread the cloth before the elders of the city.

...

But if this thing be true, and the tokens of virginity be not found for the damsel:

Then they shall bring out the damsel to the door of her father's house, and the men of her city shall stone her with stones that she die: because she hath wrought folly in Israel, to play the whore in her father's house: so shalt thou put evil away from among you. Deuteronomy 22:13-21