Making Money
While a government can issue currency, in most cases it is issued by a Central Bank. These banks are often government owned, but could also be private entities. While interesting, this is largely irrelevant to the question except to note that money doesn't have to come from a government, but regardless of source, it still has fundamental similarities.
For one, most currency issued by governments or central banks is physical. At this point, it is extremely uncommon, if not unheard of, for a government to have a digital currency as its primary currency. Physical currency is designed to be extremely difficult to duplicate, preventing - or at leas dramatically reducing - counterfeiting, whether intentional or not (as in the case of the bank forgetting to withdraw funds from an account).
At its simplest, you would deposit your physical currency at the bank, and they credit it to your account. While it may have been common practice at one time to keep the same monetary instruments (bills, coins, bars, etc) you deposited on hand so that you would later withdraw the same exact items, today the money is simply noted in a ledger by the bank. You might deposit a $20 bill with the serial number 123456789, and the next person to make a withdrawal might get that bill. If you went back later to withdraw your $20, you might get a bill with the serial number 234567890. This is fine, because in practically all meaningful circumstances, it spends the same.
Digital Currency
So, your account balance is nothing more than a number in a ledger. If the bank messes up the bookkeeping, adding (or subtracting) a 0 to the end of your account, it is between you and them to resolve it - the government is not party to the dispute.
Modern banking is significantly more complex, of course, they do not generally move physical currency between different banks, and often commit more currency than they have on balance. What does that mean?
When banks need to transfer money (say, to cash checks), they often do it in aggregate, cashing thousands of checks at once against the institution that the check is drawn upon. So, when you cash the check from your employer, your bank (assuming it is not the same bank) sends the check to your employers bank to get the money. But, there are hundreds or thousands of other people cashing checks at your bank that are also drawn upon your employers bank, and so this request is pooled together for the day and requested as one large transaction. Modern banking may work on a shorter schedule as computers can check and transfer funds very quickly, but the concept remains the same. However, at the same time, hundreds or thousands of people that have accounts at your employers bank may be cashing their paychecks from employers that maintain their accounts at your bank, and so money flows both directions. If this bidirectional flow is imbalanced at the end of the day, the bank running a deficit will be charged an interbank (or overnight) rate on the difference as the deficit is effectively treated as a loan between the banks.
The second part of this - committing more currency than the bank has on balance - is typically regulated by the government (called the reserve requirement), and applies mostly to making loans. The banks take risk when lending money - it is possible that that money is not repaid, and the bank then takes a loss. However, lending works because the vast majority of loans are repaid - the higher this amount, the lower the interest rate, in general. If this repayment percentage drops too low - that is, if people largely stop repaying loans, and thus making loans becomes too risky - then banks will stop making loans. But, lets assume that the economy is working reasonably well and loans are made. At the simplest level, lets assume that person A takes out a home loan in order to pay person B, and both people bank at the same place. From the bank's perspective, their total assets haven't changed - the ledger simply reports the money in person B's account instead of person A's. And, since the bank monetizes deposits by making loans from them, they are free to loan that money again. Indeed, since they reasonably expect to earn interest from you on the loan, they can possibly loan out a little bit more money in anticipation. This could continue repeatedly, so that the bank could potentially lend out the same money a dozen times, or more. This article provides more details on how this works.
How Governments Track Their Currency
Ultimately, governments track their currency by simply keeping track of how much they print (which is quite easy), and then how much they destroy as banks return worn or damaged (or even simply old) currency to the central bank for destruction, typically receiving shiny new currency in exchange. They might employ additional measures, such as requiring certain reporting from financial institutions, etc, but ultimately it comes down to knowing how much money was made and how much reclaimed to be destroyed, and possibly accounting for a certain percentage of loss. This article from the New York Fed provides some details of how the US manages currency flow.