Sminky and Grishka have pretty much summed it up.
In HTML, certain things get deprecated, usually because "They" have found a better way of doing it.
In recent years the trend has been to separate the functional and structural stuff from the cosmetic stuff - especially with XHTML and CSS stylesheets. So, all the stuff that actually defines how the information is structured is done in the HTML (tables, ordered and unordered lists, paragraphs, headings etc) and all the visual styling stuff is done in the stylesheets (typefaces, font sizes, colours etc).
So, things like the old font tags were deprecated to encourage people to achieve their cosmetic styling in the stylesheets - i.e. outside of the structural HTML. To separate the essential HTML from the frilly stuff.
There's a confusing middle ground where things get done both ways. It is possible to render bold text with the out-of-favour "b" tag, or it can be done in the stylesheet. On the other hand, there is a tag, "strong", that has structural value as it denotes that the text enclose within is of some importance. That tag is rendered as bold text by nearly all browsers.
So, deprecation doesn't mean that the HTML nazis regard bold or italicised text as something to be prevented, just that they think it's a good idea if it is done in a way that reflects the reason for its use: with "strong" if it is to indicate importance, or in a stylesheet if it's purely for aesthetic reasons.
I think that's sensible enough.
Note that deprecated HTML is usually still supported by modern browsers, and that is likely to remain the case: otherwise, years of valuable information published in old-fashioned HTML would no longer be visible to us.
As for underline: that is indeed best left for links. It is possible to underline text in stylesheets. IMHO the "u" tag deserves deprecation: partly because of the link confusion, but also because, IMHO, underlined text looks amateurish and horrid. Take a look at professional magazines and adverts. You'll see plenty of bold and italicised text, but very little underlining. There's a good reason for that.