Правильно: в Нови-Саде.
Склоняется вторая часть: Нови-Сад, в Нови-Саде.
2. Написание географических названий можно проверить в словарях, например в словаре Ф. Агеенко «Собственные имена в русском языке». Название, о котором Вы спрашиваете, в нем не зафиксировано, но предпочтительно: Герцег-Нови.