For which formats are Cycles materials completely and accurately exported?
OSL materials transfer best, as James pointed out.
As far as I know, Cycles cannot currently export it's own materials. Blender Internal can sure export textured things though.

Anyway if your scene is already built up with Cycles your best chance for going to 3Ds Max is first .fbx and then .dae.

About file formats:
.3ds is old.
.obj is old too, but has worked well for me, especially concerning mesh-only models.
.dae is great with textures, optimized for gaming.
.fbx is great with textures, optimised for autodesk :)
dae and fbx should probably support shaders, but as stated before, Cycles doesn't support exporting them yet anyway.

more on .dae