Prepping a cardboard box

[hnybny.livejournal.com]

I am going to try and mosaic some flat plastic/metal chips onto a cardboard box and I'd like to prep it. I want to color the box either black or white but should I use paint? I want to make sure that the glued pieces will adhere permanently and I'm worried the painted layer make flake off.

Suggestions?