Podés generarlo dinámicamente con PHP. Te dejo
un artículo muy interesante al respecto.
El sitemap lo tenés que dar de alta en Google Webmasters solo una vez, luego php lo genera cada vez que alguien (lease googlebot) trata de acceder a éste, por lo que te asegurás que en cada ingreso tenga la última "versión".
Si tu web es muy grande el método mencionado puede traerte problemas de tiempos de ejecución muy largos, por lo que un script que genere una vez al día el sitemap, o que concatene al archivo preexistente las nuevas urls es una mejor opción.
saludos!