Aftermarket Cases for Board Games
In general I try to do as little box customizing as possible, but here's some tips I've developed for storage:

Check out the fishing section of your local department store. Not for whole tackle boxes, though. You want the little plastic divided trays. There's a lot of different sizes available and most brands even have repositionable dividers for further customization.

So that takes care of the organization. And by the way, even if everything does fit back in the original box, I recommend getting these trays to organize bitsy games.

For storage, if you can't fit it into the original box (and if you're using a few tackle box trays you probably won't be able to) then you need a new box.

There are a lot of plastic tubs you can get (think halfway between a rubbermaid leftovers box for the fridge and a giant put-it-in-the-basement-and-forget-about-it box). Some places even have decent looking storage solutions. I was at walmart the other day and they have canvas-covered storage boxes in a variety of sizes that could be repurposed into game storage.

I don't really decorate my storage boxes, but if you wanted to there's plenty of images available for download from boardgamegeek.com for the particular game you're storing. You can print them out on full-page stickers and cut them out with an X-acto for an easy way to label what's in each storage box you make.

Here's a picture of what I did for Dungeon Lords:


Luckily the box was big enough that everything fits back into it. You can see the tray has moveable dividers; some of them are in place for smaller bits, some are removed so I can fit the decks of cards in. You can also see there that I decided to use one big bag for all of the wooden bits. They could be broken out by type, but they're easily divided up come game-time.

Hope this helps!