The revolutionary new idea sweeping the streets of Ankh-Morpork.
Moist von Lipwig introduced stamps to pay for the cost of a letter, and inadvertently created a crude but serviceable form of paper currency (described by Mavolio Bent as "the revolutionary unsecured one-penny note") which passes all the standard economic tests: ie, it represents the full economic value of the service provided and may be exchanged for an equivalent value of goods. And, crucially, people had now been conditioned by Moist to believe a piece of paper does have a monetary worth, far beyond that of the paper it's printed on.
From here, once Moist had become Master of the Royal Mint, with people ready to believe a piece of paper is worth its face value in gold, and everyone confident to participate in that illusion, it was no enormous difficulty to move to a paper-based currency.
The first draft was a little rough - merely a piece of paper with "$1" drawn on it, the Chairman's pawprint (see Making Money if that sounds odd) and the two legends AD URBEM PERTINET (It's All About the City) and "Promitto fore ut possessori postulanti nummum unum solvem, an apte satisfaciam." This means, roughly, "I promise one dollar to be released when the bearer asks, or I will reimburse sufficiently", which is very close to the legend "I promise to the bearer, on demand, the sum of" written on all British paper money. It is commonly held to be the case that, should the bearer of e.g. a £5 note could exchange it for £5 worth of gold in a bank and that is true provided no-one ever actually asks. Once you've got your head around that fact, it becomes clear that paper money is in fact an illusion, but one we all believe in - we have to.
This is the current state of affairs in Ankh-Morpork. It took a little while, but the small storekeepers on Tenth Egg Street gradually warmed to the idea that a piece of paper can be passed around even more easily than a small round piece of metal, becoming in turn some glitter and glue, some tobacco and some sausages whilst always remaining the same piece of paper and not losing a fraction of its worth.
Whilst paper money is new in Ankh-Morpork, it has been around for a long time in the Agatean Empire, as Rincewind found out while talking to Disembowel-Meself-Honourably Dibhala during the events in Interesting Times. Mr Bent mentioned this to Moist as a "heathen practice", but the new Master of the Royal Mint was clicking along the wheels of narrative inevitability at his usual full steam ahead pace.