First of all, the salamander is related to fire since there are ancient, almost mythological, beliefs that salamanders are unaffected by flames and could live in fire. The phoenix also has its place in mythology: it is a bird believed to have cyclically burned itself in flames, only to rise out of the ashes once again. Literally, these symbols are both related to fire and creatures who were believed to survive fire, so it makes sense they'd find their way onto these fictional firemen uniforms. Symbolically, they both, especially the phoenix, represent the idea of rebirth, which is what the resolution of "Fahrenheit 451" is all about - being able to rebuild.
The salamander was known to be a mystical creature due to its ability to live and survive in fire. This relates to Farenheit 451, for Montag is able to live and endure through the burning of books and thus knowledge.
The phoenix was another mystical creature that can be burnt, but would be born again from its ashes. This symbolises rebirth, and it relates to the novel for the wise 'book men' are heading to a beginning of a 'Renaissance', rebirth, of knowledge.