A MatCap (Material Capture) in a nutshell is a material that has color, lighting and specular information “baked” into it. They are often used in sculpting as a stand-in to setting up actual materials and lighting (since they’re lightweight realtime materials), but can also be used in a variety of other ways, including generating other materials and textures or postprocessing your renders: e.g. the model is rendered several times with different matcaps applied (or the materials are “baked” onto the textures), and later the images are combined in a painting program. A small illustration can be seen in this video by Roberto Roch.
Some releases ago Blender got a built-in matcap feature which can be enabled in the 3D View Properties panel (which you can open using N hotkey), in the Shading pane. But this feature is still limited, since users can’t supply their own matcaps, so people often use the “old way” of setting up matcaps, which can be seen in this tutorial by Ben Simonds. Incidentally, that tutorial also demonstrates how matcaps can be combined using Blender’s texture stack to create a specific look for arbitrary models.
As for applying materials/textures to complex meshes, it all, as always, depends. On how complex it is (the number of objects, are they all one mesh or separate, are they organic or mechanical, etc, etc), on topology, and, of course, on your goals. If you’re creating a full character that would be animated (for a game or for a cartoon/movie), then you’d be creating UV maps (“unwrap” the mesh) and painting (or otherwise creating) textures corresponding to those UV maps.
If it’s a render of a static object (i.e. you’re imitating a photograph of a sculpture), it may be a relatively simple material that perhaps may not use any UV maps at all (again, see the Dyntopo thread): as Craig Jones suggested above, even simple box mapping.
The level of detail you’re aiming for also comes into play, i.e. will you be using high-poly models (probably static renders) or low-poly ones (games, animations…) For low-poly maybe you’d want normal, displacement, specular maps, etc., so you’d have to bake them (in Blender or some other software).
This may sound like a lot, but as you get used to various steps involved, it mostly comes down to “what I want” and “how to get there”, as the basics stay the same no matter if you’re making a giant death robot or a cactus in a pot. There is a great deal of info on materials and texturing in Blender here on BA, on youtube, on blendercookie.com, and I’m sure many helpful artists here can help you with specific problems you might encounter.