I know everyone wants their 'pet bug' attended to first, but this one seems more potentially dangerous than most.
Consider that a users may be in violent relationships where their history is monitored by a suspicious partner. It's pretty important that that user clearly knows when they are in 'Private mode' (and not). Journalists and whistleblowers have similar issues.
I'm not a browser developer, but I can't believe that the ability to link a custom theme to private mode is a huge undertaking.