Con el Adobe after effects cs.5 pro o con Sony Vegas Pro 11, yo por experiencia persona te recomiendo el after effect pero es complicado creo que el Sony Vegas es más intuitivo, un saludo espero que te sirvan.
Con el After Effects es muy sencillo de hacer (supongo que con Vegas también pero nunca lo he usado). Básicamente se trata de disponer por un lado de la foto que vas a poner de fondo y por otro de un vídeo de unas llamas preparado para efectos (las llamas se graban sobre un fondo negro y con canal alpha aplicado por ejemplo). El AE funciona por capas como el photoshop, así que colocarías la imagen en la capa del fondo y por encima el vídeo de las llamas con algún efecto de fusión de capas ("pantalla" por ejemplo) de esta forma el color negro se hace trasparente y quedan las llamas solamente dejando ver la imagen de debajo. Puedes jugar además con la opacidad de la capa del vídeo para que se vea más o menos a través de las propias llamas también.
Ese tipo de vídeos preparados para efectos los puedes encontrar en internet en colecciones de pago (o sueltos y gratuitos buscando con calma).
Por ejemplo estos son muy conocidos y están muy bien aunque son de pago (tienen una versión más cara con vídeos en resolución 2k), pero además en la página de los creadores puedes encontrar un montón de magníficos tutoriales para AE de acceso gratuíto (eso sí, en inglés, pero se entienden bastante bien aunque no tengas mucho nivel).