A few times today, when I clicked on a link (to websites I trust, and had visited before) a little bar opened up at the bottom of the IE window. It had a "tip" that said I could turn off the underline below links in IE by going to tools->options, etc. It had a link on the right side of the "helpful tips bar" for the next tip, and a little x button on the left side to close the bar.

I scanned my computer with MacAfee antivirus, Spybot S&D, and AdAware, and none of them found anything.

Is this a new "feature" in IE or is it a virus?

I vote fishy. I haven't seen anything like that from IE, and I think I'm fully updated. Try Hijack This, usually works well for browser related spyware.

Underlining links in the browser is something some adware does. Also a lot of website do it. If you hover over/click it you get advertisments.

All links are underlined in IE by default. The issue is that a weird tip bar comes up at the bottom of the screen offering advice on how to turn off that feature.