Use Term::Cap. It's standard with all Perls (Term::ANSIColor seems to require 5.6) and it works with all terminal types, as it's based on termcap.

use Term::Cap;
use POSIX;

my $termios = new POSIX::Termios; $termios->getattr;
my $ospeed = $termios->getospeed;
my $t = Tgetent Term::Cap { TERM => undef, OSPEED => $ospeed };
($norm, $under, $bold) = map { $t->Tputs($_,1) } qw/me md us/;

print "${under}Underlined ${bold}bold$norm text (just ${bold}bold$norm
+)"'
[download]

Also of interest might be the code ue (underline end). Read the termcap manual in section 4 or 5 of your nearest UN*X system's man command for more codes than you'd have thought useful.