For this tutorial, lets start off with a black background, you can put the end result on any background you like, but for visibility's sake, we'll use black.

Lets start with a 600x200 canvas, use the paint bucket tool and fill the background layer with black

Now create a new layer by clicking the the "Create New layer icon" at the bottom of the layers pallete.

Use the rectangular marquee tool to create a selection about 1/5th of the canvas size at the bottom, and fill it with WHITE, like so...

You can now deselect the selection by pressing CTRL+D.

Now apply this filter: Filter->Blur->Guassian Blur. enter around 10 - 15px.

Now duplicate this layer 3 times. To duplicate a layer, just press CTRL+J. So now you should have 4 white blur layers in total, hide the top 3 layers by clicking on the eye icon in the layers pallete, leaving only the bottom blur layer visible. Also, select this layer as the working layer.

Now in your toolbox, select the smudge tool

Set the brushsize to about 45 px SOFTEDGE brush, and set the strength to about 70%

Now use the smudge tool to smudge the white blur layer by click and drag from the bottom up, on your way up, curve to the left or right to create the wave effect of the flame.

Now repeat this until you've smudged the whole way from left to right. In between, you may want to switch to different (smaller) brush sizes to create flame waves of various sizes.

Now, hide this blur layer, and show the next layer up.

Now repeat the smudging step for this layer, try to keep the height of your flames similar to the previous layer.

After this, you should have 4 layers of smudged white blurs, which supposedly resemble flames.

now move onto the animation part. If you are working with Photoshop 7 or older, then you need to switch to imageready to do the animation. In photoshop CS/CS2, if you dont have the animation palette open already, go to Window-> and check Animation.

You will then have an animation pallete like so...

On this first frame, we can leave as is, now lets create a 2nd frame, to do this, just click on the "new frame" icon (shown above), Now you should have 2 frames, exactly the same, but now, what we do on the 2nd frame will be different to the first frame, (hence the animation), so on the 2nd frame, hide the current displaying layer, and make 1 of the other layer visible.

So on frame 1, we have the top layer visible:

Then on frame 2, we have the 3rd layer visible:

Now create another 2 frames and disable/show alternate layers, so that each frame has a different layer visible. So now you should have 4 frames frames in the animation pallete, all different to 1 another... Just hit PLAY and you will see the animation.

This doesnt look like fire yet, lets add some colors, Click on the Adjustment Layers icon at the bottom of your layers pallete and select "Color Balance"

In the color balance settings, set the following:
Midtones: [ +60 ] [ 0 ] [ -15 ]
Shadows: [ +100 ] [ 0 ] [ -30 ]
Highlights: [ +50 ] [ 0 ] [ -30 ]

Make sure that this adjustment layer is at the very top on the layers pallete, if not, move it up there

Now, you have an animated fire effect. If you want to slow down the animation a little, you can set the delay between each frame by clicking on the down arrow at the bottom of each frame, and then select your delay time. 0.2 sec is ideal: You can also make more frames to create a smoother effect.

Now we have an animated fire, lets save it to file so we can use it on our website. Go to File->Save for Web

This will open a save for web dialog. Make sure you save it as a GIF file, then click "Save".

There you have it, an animated fire effect.
This tutorial is pretty long, so download my PSD file if you got lost somewhere:
DOWNLOAD PSD FILE