Eu fiz algumas pesquisas e criei o que acredito ser a solução específica do Nemo: criar um arquivo ~/.local/share/nemo/actions/mediainfo.nemo_action
com o conteúdo
[Nemo Action]
Name=MediaInfo
Quote=double
Icon-Name=mediainfo
Exec=mediainfo-gui %F
Selection=notnone
Mimetypes=audio/*;video/*;
Isso fará com que apareça no menu de contexto como faz com a maioria dos outros gerenciadores de arquivos. É claro que uma maneira mais genérica seria adicionar esses dois mimetypes ao arquivo .desktop, que o coloca na lista Open With.