How important is it to put decoupling caps on the same side of the PCB?
I almost always put the caps UNDER the chip on the opposite side of the PCB-- this is especially true of larger chips and higher-speed chips.

A recent design of mine uses an FPGA in a 484 ball BGA.  There are 76 decoupling caps just for that chip.  Most of them are 0.1 uF, with some 2.2 uF and 10 uF, all in an 0402 package.  18 of them are physically under the BGA, while the rest surround the chip.  Are are on the back side of the PCB.  The caps under the chip are sharing vias with the power-pins of the chip.  

Unless you are trying to save money, there is no reason to keep all components on one side of the PCB.  

Experts agree that it is more important to have your decoupling cap connected to the power/ground planes of the PCB than directly to the power pins of the chip.  This frequently lowers the overall impedance of the power traces and improves the usefulness of the decoupling caps.  After that, putting the caps closer to the chip is the next important thing.

Since a lot of my caps are sharing vias with the power pins of the chip, you can't get any closer than that!  Also, think about this...  If the via wasn't shared then half of the via would go unused.  The half of the via from the power/gnd plane to the bottom side of the PCB would not be carrying any current.  Sharing that via between a cap and the chip does not cause any extra current to be going over any via copper.  I'm not including the power/gnd plane in that because it's relatively huge and has super low impedance.

With BGA's you frequently need room around the BGA for optical inspection of the solder joints.  There are special microscopes with an angled mirror that allows for visual inspection of the balls under the part.  The mirror has to touch the PCB to get a good view, and you can't do that if there are caps in the way.  If the caps were on the same side of the PCB as the BGA then the caps would be located even farther away from the chip because of this clearance area.  So putting caps on the bottom side of the PCB, even if you don't put it directly under the chip, still gets the caps closer to the chip.

Routing of a chip, BGA or TQFP, is often easier if the caps are put on the bottom side of the PCB.  This frees up routing resources on the top side and makes it easier to fan-out the part.

I used to have the manufacturing guys complain about having caps under the chips.  They would say things like, "they'll fall off when we solder the part", "we will have difficulty reworking that part", "we can't inspect the part with X-Ray", etc.  So one time I decided to do an experiment.  I didn't place any caps under the BGA.  Once the board was up and running I compared the noise on this PCB with another similar PCB that had the same chips with caps under them.  It was obvious that caps under the chips really helped!  Ever since then I've insisted that the manufacturing guys just deal with it.  It turned out that none of the concerns from the manufacturing guys ever turned into real problems!

When putting caps under BGA's you need to carefully fan out the part in a way that makes room for the caps.  For TQFP's and the like I typically put the caps directly under the pins of the chip.  This frees up room on the PCB for other things (like vias and routing) and gets the caps as close as possible.  With TQFP's I usually put resistors and other parts next to the caps.