When should hyperlinks be underlined?

Have you noticed that more and more websites have removed underlines from hyperlinks? For example, the current beta test of Google doesn't have underlines on the search results.

Google, along with other big name websites, have slowly weeded out underlined hyperlinks over time. Why is this happening? When should we remove underlines from our designs?

Personally, I think the undecorated links on Google search results are harder to parse. The underline used to guide my eye while reading the title. Now the title and description mush together. I also felt this way when ux.stackexchange unbolded and lightened the thread titles. The titles have no prominence anymore so it's harder to scan. Who knows what's making me think this way... it may be human nature's aversion to change or it may be a genuine UI concern.

Answer

Underlined links can have a negative effect on readibility, according to this 2003 study comparing text readibility for plain text, standard blue hyperlinks and overlay link markers.

A later study comparing different link visualisation techniques found that at that time (2004) the common web user was conditioned to underlined blue links, but couldn't indicate an optimal visualisation technique.

Microsoft's guidelines about links are clear and show examples of what works for different functional patterns:

The fundamental guideline is users must be able to recognize links by visual inspection alone—they shouldn't have to hover over an object or click it to determine if it is a link.

Blue underlined text is just one of many ways to indicate that a link is a link (but because it's been the convention for so long, you really shouldn't use blue underlined text for non-links). Besides having an appropriate visual styling, other factors are context, link text and consistency across the interface.

The way I see it, the main problem with the Google test is that without the horizontal lines, the different items blend together and the visual rhythm is broken, so it becomes more difficult to scan the list. This is a basic list styling problem with many solutions (for example the iphone way of displaying lists).