The crux of the problem was the stamp paid the fee for a single usage of the mails, but the stamp itself tended to arrive at the destination in reasonably good condition; it would be the work of a moment to remove the stamp from the envelope and then attach it to another piece of mail. In the 21st century, this may seem like more trouble than it's worth; but in the 19th century, the fee for sending a letter was often a significant percentage of a daily wage.
Since letters were already receiving postmarks, the most obvious thing to do was to position the postmark so as to mark the stamp as well. This is still the most common method of stamp defacement. In many countries the postmark even comes in two parts; the location/date circle, and the "killer", a pattern of straight or wavy lines intended to mark the stamp.
More unusual methods have included tearing or slicing the stamp, but this is a slower process and can easily damage the contents, and was only occasionally used, for instance in 19th century Afghanistan.
Some enterprising individuals discovered that the postmark inks could be washed off the stamps, which set off a new round of experimentation.
In the United States, the experiment of grilling was tried in 1867, where tiny squares were embossed into the paper after the stamp was printed, the idea being that this would be break up the paper fibers and let more ink be absorbed into the paper. Unfortunately, this also made the stamps more prone to tearing, and grilling was abandoned around 1871. The more unusual types of grills are now among the great rarities of US stamps.
In Great Britain, the 1880s saw the use of fugitive inks, which were water-soluble, thus preventing washing altogether. Unfortunately, only lilac and green colors were available, and neither the public nor mail clerks liked these; it was not easy to tell different denominations apart. As with the US grills, this scheme was abandoned after a few years, and the few surviving stamps (which are easily damaged by moisture) are somewhat expensive to collect.
Later experiments involved surface coatings. Between 1901 and 1907 Austria applied varnish bars, thin diagonal strips of varnish, to the paper before printing the design. Russia did the same between 1909 and 1915, applying the varnish in a pattern of lozenges. In both cases the theory was the same; the ink of the printed design would not soak into the varnish, so that in the washing process the design would tend to flake off, forming a telltale pattern on the washed stamp.
In the modern age, the problem seems to have gone away. Postmark ink is much less soluble, and the stamps are on the average worth much less (the US first class rate stayed at three cents for over a century, from 1851 to 1958, a remarkable statistic considering inflation), so the motivation is much less than formerly.