Getting this printed at a professional print shop will be quite straightforward, given that you prepare the model nicely for printing (i.e. make it a watertight, manifold mesh).
You could print the pieces separately and assemble them later. You might also look in to getting this printed in one piece with the colors already in place on a ProJet machine, which is available as "Full Color Sandstone" on Shapeways. This might be a nice option for you.
With regards to printing the pieces separately you could go with pretty much any printing process, bearing in mind that FDM will offer the greatest range of available colors but the worst surface finish. You could try SLS instead (White Strong&Flexible on Shapeways) which is a white material that can be dyed with fabric dyes (such as RIT and Dylon) to achieve any desired color. Of course, anything you get printed (regardless of the material) could also be painted.
If you decide to get this made in FDM then make sure to choose a nice orientation for the pieces (minimizing overhangs) so you get the best quality possible. The print shop may be able to help you with this.
Getting the parts to fit together will not be a problem if you keep a little bit of clearance (around 0.2-0.5mm) between parts that interlock.