Can departmental funding combine with fellowships/grants? In trying to plan for the future and decide on preferred programs and career paths, I'm trying to figure out the seemingly Byzantine nature of how academic funding sources interact. I am particularly confused about how departmental/institutional funding effect fellowships or grant money.

To give a specific example to illustrate the general point that I'm asking about, consider this FAQ for Prospective Students at Carnegie Mellon, where it is stated anyone accepted into the PhD program can expect their tuition to be paid by the program/waived, and a stipend of ~$24k per year. The page also suggests applying for a fellowship like the PIER Program, which states it provides about a $30k stipend + $10k towards tuition. Another possibility would be something like the SMART Scholarship, which provides tuition assistance, stipend, and allows non-interfering fellowships.

This is all well and good individually, but what happens if you get department funding and a fellowship like this PIER program? Does the department keep its funding entirely and you only get the greater of the two? If your tuition is paid because of your position, does the contribution of a fellowship towards tuition just give your school some extra funding but does not effect your financial situation individually? And how does a SMART scholarship factor in?

Please note I'm not solely interested in this limited example (as it would be of interest to so few people), but more generally how this works in academia across programs and institutions. I'm in the US, though surely how this sort of thing works in other countries would be valuable to know anyway.

As a second example, consider something like a SMART scholarship and then getting a TA/RA position (which they allow) which earns tuition remittance. Does the scholarship funding source get the tuition remitted back to them, or does any part of the tuition remittance get returned to the student? 

The bottom line is deciding the real affordability of various institutions and living areas if you expect to need significantly more than a single stipend amount (raising a family, helping kids pay for their college, etc), and of course to help to decide if seeking certain scholarships and fellowships has a sufficient potential ROI for the time required to seek them.

Thank you all for any help in unraveling this Gordian knot of academic finance!
In general, the rule of funding in graduate programs is that external money is used to replace internal money. That is, if your department gives a stipend of, say, $20,000 per year, and you win a fellowship that pays $15,000 per year, the $15,000 will be used to offset part of the $20,000. 

However, most departments that I'm aware of will also guarantee that fellowship and grant holders don't suffer relative to their peers by bringing in outside money. That is, they guarantee to make up any shortfall between the value of an external award and the department's standard. (In the sciences and engineering, I would steer clear of any department that doesn't have such a policy!) Many departments will even incentivize bringing in outside award fellowships by giving a premium or bonus that supplements the outside award. This might be done either by multiplying the standard award by a percentage (so, for instance your total would be 125% of the department's standard), or by giving a lump sum on top of an outside award (if it exceeds the standard, for instance). 

One thing to watch out for, however, are restrictions placed on the outside fellowship: your department may have to certify, for instance, that you will not be assigned teaching duties or other non-research duties during the fellowship period. If you are unable to attain such a certification, the award may not be given out. 

For the PhD phase of a program, the tuition should be covered by the department and the outside fellowship; however, in general the student does not receive part of the tuition payment back. In general, the tuition charge is a negotiation between the university and the fellowship program, as this is at the graduate level usually a financial transaction. Also, if the student were to receive the tuition payment which was then forwarded to the school, this could be called taxable income, which would make things very messy for everyone.