Você deve ser capaz de seguir os prompts de instalação do LMDE sem problemas. Seu bootloader pode não estar corretamente instalado se o LMDE usar outra versão mais antiga do GRUB. Então você terá que usar um Ubuntu Live CD / USB com Boot-Repair (escolha o modo automático). Se você já tiver uma lista de sistemas operacionais após a instalação do LMDE, esta etapa não será necessária.
Sempre olhe cuidadosamente para suas partições, porque senão você pode sobrescrever sua partição Ubuntu. Prepare suas partições de disco antes da instalação do LMDE (a partir de um Live CD do Ubuntu). Para o LMDE, você precisa de pelo menos uma partição raiz (ext4 provavelmente) e uma partição swap (mas como você já instalou o Ubuntu, você pode reutilizá-lo). Use o GParted para criar uma partição raiz extra (redimensione sua instalação do Ubuntu se precisar de espaço para criar outra partição)
Você terá que tentar se o LMDE live quiser dualboot, porque eu vi cenários onde ele não queria instalar. Se for esse o caso, você não pode instalar o LMDE, mas o Ubuntu é deixado intocado, felizmente.
Boa sorte.