First of all, toString() doesn't print anything. It simply returns a String representation of the object it is called on. However, OutputStreams and Writers from the java.io package DO print. There may be a way to print in color, if your terminal supports ANSI codes. However, this would take some sophisticated manipulation of the OutputStream. Even more importantly, it seems to me that any attempt to do this would be system dependent.
Anyway, that's my long-winded way of saying that I don't know how to do it. Perhaps I've given you some ideas to think on or keywords you can google for.
google for curses. it's a time-honored Unix library meant to alleviate some of the platform-dependency of this sort of thing; basically, it's an abstraction library meant to translate between platform-independent, higher-level notions (even some text-mode "GUI" widgets!) and whatever the machine-dependent lower layers need.
as far as i can tell (mostly from this JavaWorld article) you'll likely still need to use JNI to access a curses implementation. but at least you won't have to hardcode ANSI escape sequences in your code, and curses has been ported to Windows, so it's quite widely available.