Physical Money
M0 is just paper and metal. The paper is printed in D.C. and Fort Worth by the Bureau of Printing and Engraving and banks purchase it using electronic money they have in their federal reserve deposit accounts. Nothing special there and the effective money supply doesn't really change when M0 changes.
How the Fed Increases the Money Supply
What it sounds like you are asking is how the Fed increases the money supply in general. The Fed is constantly buying, selling, lending, and borrowing. It does this through its open market operations desk at the NY fed and through other mechanisms such as lending to banks at the discount window and paying interest on deposits at the fed. At any time you can look at how much money is flowing out of the fed (purchases, loans, and interest) and how much is flowing in (sales, redemptions, and borrowing) and compute the difference. If they are buying and lending more than they are selling and borrowing, the money supply increases. That's how it happens and it is going on continuously. Sometimes they buy things for above their market price (or push the price up) if they are trying to inject a lot of money into the supply or buoy up a particular market.
If the Fed increases the money supply in general, then it is possible that the number of physical dollars in use will increase, which means the Bureau of Printing and Engraving needs to spit out some more paper. This is not that important of a consequence, though. The spitting out of paper is not what increases the money supply. Every physical dollar is purchased with an electronic dollar, so the effective money supply does not change.
Where Fed Dollars Come From
The key to understanding the Fed is to remember that they are the only institution that doesn't really have a budget constraint. When they buy something, they create brand new dollars to do so. When they sell something, the dollars they receive effectively disappear. Every other institution, including the federal government, must actually have dollars to spend or get them via borrowing. Because of this property, every time they buy something or make a loan, the money supply increases.
By the way, the fact that the Fed can make up and destroy money is why it makes little sense to worry about or discuss the Fed's balance sheet. It's the unique institution with the property that its balance sheet doesn't need to affect its behavior.