A little update for the year 2015
TL;DR answer:
Go to Settings -> Editor -> File Encodings -> Project Encoding and set it to "UTF-8".
Expanded answer:
The reason why it does not work can be found by placing a breakpoint on a System.out.print() call. When the breakpoint hits, you can add System.out to Watches, and you can see that System.out.textOut.out.se.cs is set to windows-1252 or something similarly unsuitable.
The setting which magically worked for me (I do not know why) is in Settings -> Editor -> File Encodings -> Project Encoding. You need to set that to "UTF-8".
Then, unicode characters display properly on the console, and one more quick look with the debugger shows that the value of System.out.textOut.out.se.cs has magically turned into UTF-8.
I am saying "magically" because I do not see how and why an editor setting should affect the character set that System.out gets instantiated with when launching/debugging an application. If someone knows what is the logic behind this, please do tell!