Is it normal to have a rats-nest of VCC/GND traces under an IC?
What you're missing is the use of a power plane.  It appears you're using Eagle, use the polygon command to create a plane, and name it GND.  Then, use the ratsnest command to pour this plane over your board.

For a 4-layer board, you should have an internal GND layer and an internal VDD layer.  Route your signals on the outer layers, and pass vias through to the planes near the pads.  

For a 2-layer board, the issue becomes more complicated.  It's quite easy to set up loops (which are bad for signal integrity and EMI) when routing signals through a power layer.  

The IOIO is an example of a 2-layer design with good routing.  The bottom layer in this image is GND;  I've edited this to use a 3.3V plane under the IC instead of their original traces.  You can get the un-edited orignal documentation (including layout files) here.



They placed the decoupling caps rather far away.  Presumably, this was done so that all parts could be placed on the top layer. If you can solder on both sides it's probably better to locate them directly under the IC, and connect with short vias to the associated pins. 

Also note that their voltage regulator and its associated 10uF decoupling cap are barely off-screenshot to the right.  If they were any further, I'd also add a bulk cap of 10uF or so immediately under the IC, in addition to the 0603s shown.

Finally, note that even though there's a large, low-impedance plane under the IC, it's fed by two 8 mil traces under two pads at the right side.  If I was being extra-careful, I'd have moved the LED and resistor at the right, as well as the 5V trace coming in across the right corner, to get a lower-impedance connection through that gap.