IMAP doesn't really support multiple charsets (just looked at RFC 3501).
 There are two places where character sets other than ASCII is used. 
One is in the SEARCH command; there's an optional parameter which can
indicate that the search strings are in a non-ASCII character set.  The
other is in transmission of message literals (email messages) back and
forth.

So probably setting the default encoding at this level isn't quite
right, as you should definitely be reading raw bytes from the socket,
not characters, but it isn't too far off.  Looks like _command() needs a
bit of work (it shouldn't try to quote bytes, only strings), and the
documentation need to be improved, to say that non-ASCII search strings
and message bodies should be passed as bytes encoded according to the
specified CHARSET, but with those fixes it should work.  Assuming that
bytes are hashable in Python 3K.