Sorry for this whole bunch of questions. Please note, that I know what a commutative diagram is, and that I can somehow read them, at least the simpler ones. But often enough the diagrams are labelled and/or explained verbally, thus my question:

How are commutative diagrams to be read in general? Can they always be deterministically translated into first-order sentences or properties?

Which "background assumptions" are needed for a commutative diagram to make specific sense? (A minimal assumption should be that they tell something about a category. What else?)

Which conventions are used? (e.g. for existence and uniqueness of arrows)

When is it important to label the objects and arrows?

When are verbal explanations necessary?

Does every conceivable diagram mean something?

Are there (graphical) analogues of commutative diagrams for other (relational or algebraic) structures than categories?

-
You are asking questions of a general nature, but there is no "general theory of diagrams" nor even a established set of conventions with regards to them---different authors will do different things. If you have a specific problem, describing it would help muchly in coming up with useful answers. Otherwise, there is very little concrete to be said, really, apart from «practice makes perfect»: you can now understand "simpler" diagrams... with time, you'll learn o deal with the not so simple ones too! – Mariano Suárez-Alvarez Feb 16 '11 at 16:06

Commutative diagrams are, to put it simply, a (very) handy way of writing systems of equations in categories. Instead of having rows of symbols and do symbol-pushing you reason diagramatically and geometrically.

Now, about your questions, I am not sure I understand all of them so my answer may be way off, but here it goes anyway.

Which "background assumptions" are needed for a commutative diagram to make specific sense?

Without going (too) technical here, diagrams in categories are oriented graphs where the vertices are labeled with objects and the edges with arrows and to every path we associate the composite arrow. The problem is that the composite is not well defined in the presence of loops, e.g. think of a single vertex with two loops labeled f and g: does it denote the composite fg or gf? If your labeled graph does not have loops then you are all set.

Note: making this all formal and rigorous is something of a chore and for a little gain. One possible way is to define diagrams of shape $G$ (a graph, for example a square) in a category $A$ as functors $FG\to A$ where $FG$ is the free category on the graph. Then a commutative diagram of a shape $G$ is a functor $FG/R \to A$ where $FG/R$ denotes the quotient of $FG$ by a congruence $R$ that "forces" commutativity, that is, the equality of certain (all) parallel pairs of paths. You can then define the gluing of diagrams along a common diagram as a certain pushout, which allows you to prove that if the smaller pieces of a diagram are commutative then the whole thingy is also commutative, etc.

Which conventions are used? (e.g. for existence and uniqueness of arrows)

I am not sure understand what you are trying to ask here. What problem of existence and uniqueness are you referring to? The existence and uniqueness of a composite associated to a path was treated in the previous answer.

When is it important to label the objects and arrows?

Unless there is no ambiguity about what arrows and objects you are mentioning (or you simply do not need them), feel free to not label the graph. In my experience, this happens very rarely so I tend to label just about everything.

When are verbal explanations necessary?

No general rule here. The best that I can offer is use common sense and know your target audience.

Does every conceivable diagram mean something?