Underlining search results in vim (instead of highlighting them)

You need to modify the highlighting for the 'Search' syntax element. You can do that with a command like this:

:highlight Search guibg=black guifg=yellow gui=underline

That command will set the text color (i.e, foreground) of the found search words to yellow (againt black background) and will underline them. The command above alters only the highlighting for the gui, which means in gvim. Altering in terminal, I think would be this:

:highlight Search ctermbg=black ctermfg=yellow term=underline

As another answer noted, you can set the syntax highlighting of search results by targetting Search

:highlight Search guibg=guibg guifg=guifg gui=italic,underline,bold

Setting the guibg and guifg to themselves should undo any gross colors that may be showing. If you want the results to be more/less noticeable you can tweak the gui settings (:help highlight-args for details). If you want the bg and fg colors reversed in a theme-friendly way you can use gui=inverse.