You're obviously looking at the right place, Orion. I'm a bit puzzled because none of my books have underlined headers or footers. So I suggest that you play about with the header and footer options under "options."
I just have the title as a header and it isn't underlined. Perhaps the underlining is only with author and title? I choose the chapter titles for footers and they don't get underlined either. So I'm supposing that it depends on what precisely one chooses.