Whee
Ok this is a tut for Gimp.
First, make a new image, and a new transparent layer.
Use the lasso tool to form a sort of weird shape.
Fill it with dark red, and shrink it by however much you want.
With each layer of selection shrinkage, fill it with a lighter color.
You can also make it get darker somewhere inside it like this.
Now, use Filter->Blur->Gaussian Blur...
Get it as blury as you please; use RLE thingy.
Now make two more transparent layers ontop of the fire layer.
Fill both of these layers with clouds (Filter->Render->Clouds->Solid noise...)
Make sure that detail is set to 15.
Also make sure that each layer has a different bunch of clouds.
Now, select the fire layer again.
Go to Filter->Map->Displace
Set the X Displacement to one of the cloud layers, and Y Displacement to the other. Don't use the same one, that'd be stupid.

Set the X and Y Displacement values to however much looks good.
Click OK and delete your two cloud layers. Tada!