It depends.

If you're using Java2D you might find it too slow to rotate a single sprite each time you display it, in which case pre-rotated would obviously be the way to go. If you're using OpenGL /
LWJGL then it'll be plenty fast enough to do it on the fly. But if you're running at a low resolution or with tiny sprites then for best quality you might still prefer to have lots of sprites drawn at specific angles. This tends to depend on your style of art though (and whether you can find an artist willing to do all the extra work!).