Check out the Java2D rendering capabilities and
its ability to move, scale and anti-alias stuff.
As a result the rendering result of the individual
steps should look smooth.

Many animations are frame-based, where you increase
the pixel position (or subpixel position) for
every new step. The movement speed then depends
on the rendering engine and the machine state.
For example some garbage collection algorithms
pause for a quite long time.

An alternative is to use a time-based animation.
I provide a free open source animation library
for time-based animations. It ships with a tutorial
application that does something similar to the
Metamorphosis intro, see
http://www.jgoodies.com/freeware/metamorphosis/
http://animations.dev.java.net/

Hope this helps,
Karsten

Use double buffering maybe.

use double buffering technique to avoid flickering, adjust sleep intervals
to aprox. 30 miliseconds, and move image only few pixels in each frame.

sample code:

Graphics offscreen;
Image offImage;
Image myGif;

public void run()
{
   offImage=createImage(300,300);
   offscreen=offImage.getGraphics();
   int x=0;
   int y=0;
   while(running)
   {
       offscreen.drawImage(myGif,x,y,this);
       repaint();
       x++;
       y++;
       try{Thread.sleep(30);}catch(Exception e){}
   }
}

public void paint(Graphics g)
{
   g.drawImage(offImage,0,0,this);
}

public void update(Graphics g)
{
   paint(g);
}