I've got a JAVA based game with an OpenGL rendering front that is drawing a large amount of sprites every frame (during testing it peaked at 700). Now this game is completely unoptimized. There is no spatial partitioning (so a sprite is drawn even if it isn't on screen) and every sprite is drawn separately like this:

graphics.glPushMatrix();
{                  
    graphics.glTranslated(x, y, 0.0);                           
    graphics.glRotated(degrees, 0, 0, 1);

    graphics.glBegin(GL2.GL_QUADS);

    graphics.glTexCoord2f (1.0f, 0.0f);
    graphics.glVertex2d(half_size , half_size); // upper right

    // same for upper left, lower left, lower right
    graphics.glEnd();                   
}
graphics.glPopMatrix(); 

Currently the game is running at +-25FPS and is CPU bound. I would like to improve performance by adding spatial partitioning (which I know how to do) and sprite batching. Not drawing sprites that aren't on screen will help a lot, however since players can zoom out it won't help enough, hence the need for batching. However sprite batching in OpenGL is a bit of mystery to me. I usually work with XNA where a few classes to do this are built in. But in OpenGL I don't know what to do.

As for further optimization, the game I'm working on as a few interesting characteristics. A lot of sprites have the same texture and all the sprites are square. Maybe these characteristics will help determine an efficient batching technique?