The answer really depends on whether this game is 2D or 3D.
If your game is 2D, an easy way to do what you want is to use Java's own 2D Graphics API. A good tutorial to start you off (at least in my opinion) can be found at The Java Tutorials. In my experience I have found that Java's graphics API is easy to learn, and is more efficient than one might expect. The basic technique is to have your game code keep track of the positions of all your objects, then translate those coordinates into screen coordinates and display appropriate images at those locations. I made a (very, very simple) game in Java once, and this is the method I used.
If your game is in 3D, OpenGL is definetly the way to go. I have only limited experience with OpenGL, so I'm not sure how easy the Java bindings are to work with. In general, 3D programming is a massive topic, so if this is a first-time project or you aren't prepared for a major time investment, I would attempt to find a good game framework to use or make the game 2D. If you are interested in OpenGL, or 3D programming in general, a quick Google turned up the JOGL project. I would recommend investigating JOGL as a way to access the OpenGL API from within Java code, but for actually learning OpenGL I recommend The OpenGL SuperBible(5th edition), commonly known as "The Blue Book".
The code examples are all in C++, but for the OpenGL functions it could possibly be just a matter of using a wrapper library. For example:
Unfortunately I can't give concrete examples because I haven't used OpenGL with a Java program, but the above example very coarsely approximates how OpenGL ES is used on the Android platform.
As far as performance... Java's API comes with a non-trivial ammount of overhead, but I could see it doing alright for your purposes. You may have to put a little more effort into making your algorithms efficient, and your game may not run as well on less-capable hardware. If you do decide to go the OpenGL route, it will almost certainly be much faster (again, depending on how efficient your algorithms are), but is correspondingly much harder to learn and get started with. Certainly doable, but it will be a challenge.
The 5th edition of OpenGL SuperBible has been recently released. This edition reflects OpenGL 3.3 which was released at the same time as OpenGL 4.0, the book only covers the core profile and assumes no prior OpenGL knowledge.
That's what I got from the book's description anyway. I have the 4th edition and it's an excellent resource for OpenGL 2.0, so I assume the new edition along with the latest OpenGL Shading Language book would be just what you're looking for.
Durian Software has an ongoing series of tutorials covering modern OpenGL. They are aimed at OpenGL 2.0 but avoid using any deprecated functionality in later versions.
NeHe is in the process of writing new tutorials. Some of the things you may have been used to 10 years ago have been more or less abandoned (compatibility profiles are still around, but they're deprecated) in moving to a fully-programmable pipeline and more efficient primitives.
For example, passing vertices between glBegin()/glEnd() is being left behind in favor of vertex buffer objects and vertex arrays. The old transform and lighting model is going away in favor of fragment shaders.
I'd suggest starting with Joe Groff's intro to modern OpenGL, and get a copy of The OpenGL SuperBible, 5th edition, which covers all of the new ways of doing things.