How and when is M0 money created? The Federal Reserve Coin and Currency Service Website
describes their currency order process thus:

The 7.2 billion notes included in the FY 2015 order reflect the Board’s estimate of net demand for currency from domestic and international customers.
The print order is determined, by denomination, based on historical
payments to and receipts from circulation, destruction rates, and also
to build inventories of new-design notes before issuance.
Historically, most of the notes that the Board orders each year
replace unfit currency that Reserve Banks receive from circulation.
The estimated number of notes that Reserve Banks will destroy accounts
for nearly 85 percent of the proposed FY 2015 print order and includes
both unfit currency, as well as all old-design $100 notes received
from circulation.  The expected growth of Reserve Bank net payments
(payments less receipts) to circulation primarily accounts for the
remainder of the notes in the FY 2015 print order.

From this description, it is unclear to me how and when M0 Money is created. It seems this is tied to 'Reserve Bank net payments'.
How and when is M0 money created?
First it is helpful to provide some definitions.

M0 includes all paper dollars (plus coins and US notes).  Regardless of whether or not they they are held in the banking system.

M0 is not a useful metric because it omits electronic dollars.  The two main liabilities to the Fed are electronic dollars (some refer to them as Fed Funds or deposits at the Fed which banks can hold) and paper dollars.

M0 + electronic dollars = MB.  MB is by far a much better metric for measuring what the government has created for money.

The Fed's balance sheet may be illustrative in showing how this works. Much of the Fed liabilities are MB, but only a much smaller part are M0. The difference between paper and electronic dollars is not significant.  If a bank asks the Fed to trade their electronic dollars for paper (or vice versa, the Fed will oblige.  If the Fed runs short on paper, they will have the treasury print more, but this doesn't expand MB.

Think of paper dollars as ice, electronic dollars as flowing water and MB as all the water in the system (frozen or flowing).  Whatever the form, it is not important as the total amount of water remains the same.  

Let's try to answer our question specifically using a timeline and ledger entries.

Say the Fed buys some assets from a bank.  They acquire these assets (+Fed assets) and grant the bank new deposits (+liabilites aka bank deposits).  Now this is always done with electronic dollars to start.

Then say the bank has a lot of withdrawals and wishes to convert some of their federal despots assets into cash assets.  They ask the Fed to do this, which gladly obliges.  The Fed decreases their deposit liability and increases their paper note liability.  In this moment M0 was increased.  But it is not significant.  What was significant was when MB was increased after the Fed acquired the asset from the bank.