OK, le puse imágenes, de la manera mas sencilla posible y todo, pero si no se entiende algo o te queda alguna duda, avisas:
1- Primero, crea una copia de ese GIF que quieres usar, y esa copia la abrirás con el Adobe Fireworks. Para el ejemplo yo usaré estos elementos en el tutorial:

GIF

Fondo que quiero agregar

Algo que irá encima del GIF, ocultando parte de este.
2- Una vez ahí, ubica la pestaña de herramientas
Capas, es fundamental para hacer este truco.

3- Usa el botón de Capa Nueva, y crea 2 capas.

4- Ordena las capas como lo demuestra la imagen.

5- Agranda el lienzo para que puedas trabajar en la imagen ahora que las capas están creadas.

6- Clickea la capa de abajo y pega tu fondo, lo mismo con la imagen que se iba superponer, pero en la capa de arriba. Alinealos como desees, pero solamente esas cosas,
NO MUEVAS NI ACOMODES LA IMAGEN DEL MISMO GIF, sino se arruinará. Finalmente, como dice en la imagen, ajustas el lienzo. La verdad es todo muy sencillo.

7- Ahora en
Archivo > Guardar como..., buscas la ubicación donde guardarlo, le das nombre etc, y en la barra desplegable
Guardar eliges esta opción:

Es importante que lo grabes en Fireworks PNG, ya que si deseas editar el GIF en el futuro, tendrás que hacerlo desde este archivo, que contiene las capas por separado y todo.
8- Ahora que tienes el archivo original, solo te hace falta guardar el mismo archivo en formato
GIF animado, este será el archivo que se verá animado en tu computadora y podrás subir a Internet

Te recomiendo que en la pantalla de guardado te tomes el tiempo de ir a
Opciones y elijas las siguientes especificaciones:

Dale a Aceptar y grabalo.
---
Espero que se haya entendido.