Perdon, si me falto algo:
Código PHP:
ResultSet rs=st.executeQuery("select count(*) from usuarios");
rs.next();
System.out.println("numero de renglones: "+rs.getString(1));
Perdon por contradecir a B** pero no es necesario hacer ningun bucle con que le agreges el rs.next() al codigo que te mande funciona, se que hay varias maneras pero, en lo personal esta es la mas facil, ademas el conteo de renglones empieza en 1, bueno, solo puedo hablar de postgresql y ms sql server que son lo que he manejado
EXITO!!! (espero :)