Nom the dog was introduced during episode 410, when he sang to an earworm tune “nom nom nom”. At some point it was suggested to name him “Marflebark” but the name Nom - as suggested by Ezra - stuck.