Saludos!!
Primero que nada, tienes los codigos al reves! no es <li><ul>Mi Titulo</ul></li> sino que es <ul><li>Mi Titulo</li></ul> Luego de eso, puedes ponerle un <h2> al Titulo y ponerle al CSS li h2 {text-decoration: underline } y asi solo el titulo tendra el subrayado.
Hasta Luego!!
EDITO: Porque no ves
Este documento que habla sobre las listas desordenadas? Segurmente te ayudara bastante.