The Penny Black was the world's first adhesive postage stamp. It was issued by the United Kingdom on the first of May 1840 and used from the sixth May of the same year. All London post offices received official issues of the new stamps, but other offices in the country did not. Some post offices like in Bath, offered the stamp unofficially after May 2.
Once the stamps were used, they had a red cancellation. However, it was hard to see, and it could easily be taken off. It is not very rare, although prices vary from a few pounds to over 1000000 pounds.