I'll leave the doc questions for Fred (maybe better open a SF bug for them though). Then:
From what I could find in the docs, it's completely non-obvious how the following works for immutable objects in containers:
x = [ 1, 2, 3] x += 3 x
[1, 5, 3]
Is the sequence of operations described someplace?
Um, in the code. :-( Using dis(), you'll find that x+=3 executes the following:
6 LOAD_FAST 0 (x) 9 LOAD_CONST 1 (1) 12 DUP_TOPX 2 15 BINARY_SUBSCR 16 LOAD_CONST 2 (3) 19 INPLACE_ADD 20 ROT_THREE 21 STORE_SUBSCR
How does Python decide that sequence elements are immutable?
Huh? It doesn't. If they were mutable, had you expected something else?
>>> x = [, , ] >>> x +=  >>> x [, [3, 6], ] >>>
Basically, += on an attribute or subscripted container does the following:
(1) get the thing out (2) apply the inplace operation to the thing (3) put the thing back in
The inplace operation, of course, is a binary operator that *may* modify its first operand in place, but *must* return the resulting value; if it modified the first operand in place, it *should* return that operand. If a type doesn't support an inplace operation, the regular binary operator is invoked instead.
Does this help? (The whole thing is designed to be intuitive, but that probably doesn't work in your case. :-)
--Guido van Rossum (home page: http://www.python.org/%7Eguido/)