What would be the correct translation of the song title "New Moon on Monday" to Latin? Word for word with the same structure as English seems like it would be something like "Nova Luna in dies Lunae", although I don't know if I'm using the right gender and case, etc.
Your suggestion nova luna in dies lunae is "new moon into Mondays". It is grammatically valid, but does not mean what you want.
A new moon would be luna nova or nova luna. Latin typically puts the adjective last, but it is not a hard rule.
Monday is dies lunae, literally "day of the moon". When you decline this, you only change dies ("day") and leave lunae ("of the moon") untouched. A time is usually expressed in Latin with a plain ablative without any prepositions, and that would be the only grammatical choice here. Therefore "on Monday" would be die lunae.
The most direct and prosaic way to say "new moon on Monday" is luna nova die lunae. This also looks nice as the moons frame the rest of the phrase. You can also put the moons next to each other: die lunae luna nova.
If you use interlunium for new moon instead, it just replaces luna nova in the expression. While interlunium is classically preferable, it might be less clear a concept in modern use for most readers than luna nova.