In the tutorial, at http://docs.python.org/tutorial/classes.html#private-variables you can read:

----
9.6. Private Variables
“Private” instance variables that cannot be accessed except from inside an object don’t exist in Python. However, there is a convention that is followed by most Python code: a name prefixed with an underscore (e.g. _spam) should be treated as a non-public part of the API (whether it is a function, a method or a data member). It should be considered an implementation detail and subject to change without notice.

Since there is a valid use-case for class-private members (namely to avoid name clashes of names with names defined by subclasses), there is limited support for such a mechanism, called name mangling. Any identifier of the form __spam (at least two leading underscores, at most one trailing underscore) is textually replaced with _classname__spam, where classname is the current class name with leading underscore(s) stripped. This mangling is done without regard to the syntactic position of the identifier, as long as it occurs within the definition of a class.

Note that the mangling rules are designed mostly to avoid accidents; it still is possible to access or modify a variable that is considered private. This can even be useful in special circumstances, such as in the debugger.

[...]
----

I think that this section doesn't stress enough how special the "__foo" syntax is and how rarely it should be used. If I was a programmer coming from Java to Python, I would start using "__foo" everywhere after reading this. I actually receive code written like that from programmers new to Python, and they point to that section of documentation when I ask why they did it.

At minimum, I'd add a paragraph that warns about how name mangling makes the code hard to reuse, difficult to test and unpleasant to debug.

No warnings, please.  See http://docs.python.org/documenting/style.html#affirmative-tone and related sections.

But at the least, the start of the para might be slightly reworded to something like: "If you specifically need to avoid name clashes with subclasses, there is limited support..." which avoids the phrase "Since there is a valid use-case for class-private members".

"In the unlikely case that you specifically need to avoid name clashes with subclasses, there is limited support..." ;)

I think the main problem here is that they are called "private" and people coming from other languages assume that the double underscore is the Python way to mark variables as private, whereas the appearance of being private is just a side effect of the name mangling.

This part should IMHO focus on the name mangling, explaining what it is and what it's useful for, and mention clearly that this doesn't really make the variable "private", because it can still be accessed through the mangled name.

The section could also mention that the word "private" here doesn't mean the same thing as in other language.

I don't know if the "trust the programmer" philosophy found in Python is explained somewhere in the doc, but if not it could be added to the tutorial or the FAQ.

I'd like to see that section gone altogether. The tutorial is designed to be the first point of contact with the language. In that context name mangling is an obscure detail with an unlikely use case.

If anything, the tutorial should simply state that private variables are by convention prepended with a single underscore. Maybe there's place for a separate short article which would nicely explain the philosophy behind the lack of an enforcing `private` modifier. The "we're all consenting adults here" stuff.

Agreed with Ezio that "private" is in itself a poor name for what underscore (regardless whether a single one or two) really means.

This is a venerable section of the tutorial that has been exposed to many, many readers and AFAICT it has never caused a problem.  So, I see no need to make a change to it.

Also as Georg points out, the docs (especially the tutorial) are not about discouragement, they are about empowerment.

I am reporting this specifically because I just had two independent cases of people who submitted code that had almost all methods name-mangled (within 2 weeks), and who then pointed to that section of the tutorial as justification. I have a hard time convincing them that it is a bad idea, as I have to work against the official documentation here. 

I agree that the language and library references should explain the mechanics behind the language in a neutral and empowering way. But I think that tutorial shouldn't tell people to write horrible code.

Perhaps it would suffice if the tutorial didn't call this "private methods"? A more descriptive and accurate section name, such as "name mangling" or "avoiding name clashes" could help a lot.

FWIW that section used to be called "Private variables through name mangling" back in 1.5, and started by saying "There is now limited support for class-private identifiers.".

PEP8 [0] also talks about the name mangling in several places, and carefully avoids the use of "private":
  """
  To avoid name clashes with subclasses, use two leading underscores to
  invoke Python's name mangling rules.

  Python mangles these names with the class name: if class Foo has an
  attribute named __a, it cannot be accessed by Foo.__a.  (An insistent
  user could still gain access by calling Foo._Foo__a.) Generally, double
  leading underscores should be used only to avoid name conflicts with
  attributes in classes designed to be subclassed.
  """

And it even includes the following two notes:
  """
  We don't use the term "private" here, since no attribute is really
  private in Python (without a generally unnecessary amount of work).
  """

  """
  Not everyone likes name mangling.  Try to balance the
  need to avoid accidental name clashes with potential use by
  advanced callers.
  """

[0]: http://www.python.org/dev/peps/pep-0008/

New changeset 68bc3c5960a4 by Raymond Hettinger in branch '2.7':
Issue 12086: add example showing how to use name mangling.
http://hg.python.org/cpython/rev/68bc3c5960a4

New changeset 79f9698777b7 by Raymond Hettinger in branch '3.2':
Issue 12086: add example showing how to use name mangling.
http://hg.python.org/cpython/rev/79f9698777b7

New changeset fca745bc70be by Raymond Hettinger in branch 'default':
Issue 12086: add example showing how to use name mangling.
http://hg.python.org/cpython/rev/fca745bc70be

Added an example of how to use double underscores correctly.  

I agree with Ezio that the rest of the documentation is clear on the subject.