A re-financing, or re-fi, is when a debtor takes out a new loan for the express purpose of paying off an old one. This can be done for several reasons; usually the primary reason is that the terms of the new loan will result in a lower monthly payment. Debt consolidation (taking out one big loan at a relatively low interest rate to pay off the smaller, higher-interest loans that rack up, like credit card debt, medical bills, etc) is a form of refinancing, but you most commonly hear the term when referring to refinancing a home mortgage, as in your example.
To answer your questions, most of the money comes from a new bank. That bank understands up front that this is a re-fi and not "new debt"; the homeowner isn't asking for any additional money, but instead the money they get will pay off outstanding debt. Therefore, the net amount of outstanding debt remains roughly equal. Even then, a re-fi can be difficult for a homeowner to get (at least on terms he'd be willing to take). First off, if the homeowner owes more than the home's worth, a re-fi may not cover the full principal of the existing loan. The bank may reject the homeowner outright as not creditworthy (a new house is a HUGE ding on your credit score, trust me), or the market and the homeowner's credit may prevent the bank offering loan terms that are worth it to the homeowner. The homeowner must often pony up cash up front for the closing costs of this new mortgage, which is money the homeowner hopes to recoup in reduced interest; however, the homeowner may not recover all the closing costs for many years, or ever.
To answer the question of why a bank would do this, there are several reasons:
The bank offering the re-fi is usually not the bank getting payments for the current mortgage. This new bank wants to take your business away from your current bank, and receive the substantial amount of interest involved over the remaining life of the loan. If you've ever seen a mortgage summary statement, the interest paid over the life of a 30-year loan can easily equal the principal, and often it's more like twice or three times the original amount borrowed. That's attractive to rival banks.
It's in your current bank's best interest to try to keep your business if they know you are shopping for a re-fi, even if that means offering you better terms on your existing loan. Often, the bank is itself "on the hook" to its own investors for the money they lent you, and if you pay off early without any penalty, they no longer have your interest payments to cover their own, and they usually can't pay off early (bonds, which are shares of corporate debt, don't really work that way). The better option is to keep those scheduled payments coming to them, even if they lose a little off the top.
Often if a homeowner is working with their current bank for a lower payment, no new loan is created, but the terms of the current loan are renegotiated; this is called a "loan modification" (especially when the Government is requiring the bank to sit down at the bargaining table), or in some cases a "streamlining" (if the bank and borrower are meeting in more amicable circumstances without the Government forcing either one to be there). Historically, the idea of giving a homeowner a break on their contractual obligations would be comical to the bank. In recent times, though, the threat of foreclosure (the bank's primary weapon) doesn't have the same teeth it used to; someone facing 30 years of budget-busting payments, on a house that will never again be worth what he paid for it, would look at foreclosure and even bankruptcy as the better option, as it's theoretically all over and done with in only 7-10 years. With the Government having a vested interest in keeping people in their homes, making whatever payments they can, to keep some measure of confidence in the entire financial system, loan modifications have become much more common, and the banks are usually amicable as they've found very quickly that they're not getting anywhere near the purchase price for these "toxic assets".
Sometimes, a re-fi actually results in a higher APR, but it's still a better deal for the homeowner because the loan doesn't have other associated costs lumped in, such as mortgage insurance (money the guarantor wants in return for underwriting the loan, which is in turn required by the FDIC to protect the bank in case you default). The homeowner pays less, the bank gets more, everyone's happy (including the guarantor; they don't really want to be underwriting a loan that requires PMI in the first place as it's a significant risk).
The U.S. Government is spending a lot of money and putting a lot of pressure on FDIC-insured institutions (including virtually all mortgage lenders) to cut the average Joe a break. Banks get tax breaks when they do loan modifications. The Fed's buying at-risk bond packages backed by distressed mortgages, and where the homeowner hasn't walked away completely they're negotiating mortgage mods directly. All of this can result in the homeowner facing a lienholder that is willing to work with them, if they've held up their end of the contract to date.