Windowed Java2D games will never be as smooth as full screen ones.
The Brackeen example posted above is silky smooth on my AMD64 3000+, but jerks slightly on my other P3 600.
I actually have the Brackeen book and the 2D engine he builds is pretty good and a nice example of good OOP design without getting too complicated. He uses vanilla Java2D for everything.
Basically, to get smooth animation in Java2D he does the following:
1. Use setFullScreenWindow() to enter full screen exclusive mode.
2. Use a BufferStrategy with 2 buffers. This will automatically use page flipping if the hardware supports it (which virtually all cards these days do). Page flips will synced to the monitor vertical retrace by default. If page flipping is not available it will use double-buffering, which is a lot slower.
3. Use a NullRepaintManager which catches AWT repaint requests and discards them, so they don't conflict with your own rendering.
4. Use floats for your x, y coords, not integers.
Even after doing all this you may still find motion jerky for another reason: the granularity of System.currentTimeMillis on Windows XP is 10-15ms, on Win9x it is a whopping 55ms. This means that you cannot always rely on getting precise times for your update code, which translates to jerkiness on the screen.
Brackeen gets around this by using a TimerSmootie class which averages out the values returned by the last few calls to currentTimeMillis. This results in noticeably smoother animation. However, this technique is only useful for games in which the frame rate is fairly consistent. If it varies wildly, the average values will be skewed, giving innacurate results.
It could be improved further by using a higher resolution timer, for which several alternatives exist under Windows:
1. Java 5.0 includes one, however, you might not want to force your users to Java 5.0 just for this feature.
2. The AdvancedTimer in GAGE (http://java.dnsalias.com/
3. LWJGL has a hi-res timer.
Other stuff to think about: remember Java2D is not a games framework, it's a general purpose graphics library and hence will contain overhead. The alternative is to use something like LWJGL. This does not rely on Java2D, Swing or the AWT for events. So the overheads are a lot lower. Additionally it uses OpenGL for hardware accelerated graphics. The problem is that there is a steep learning curve if you don't know OpenGL.