¿Crear una tabla nueva o contar filas?¿Qué opción recomiendan?

[gnzsoloyo]

Cada grupo puede tener muchos USUARIOS y un USUARIO solo puede pertencer a un grupo.

Eso sólo requiere formalmente que la FK del grupo de pertenencia esté en la tabla USUARIO.

Si yo quisiera mostrar una lista de GRUPOS con la cantidad de usuarios que tienen cada uno tengo que recorrer la tabla de USUARIOS por cada grupo.

No tienes nada que recorrer. No entiendo por qué lo dices.
¿Nunca has usar GROUP BY?
Algo tan simple como esto lo puedes encontrar en cualquier tutorial básico:

Código MySQL:

SELECT G.grupo_id, G.grupo_nombre, COUNT(U.usuario_id) cantidad
FROM grupo G INNER JOIN usuario U ON G.grupo_id = U.grupo_id
GROUP BY G.grupo_id
 

No necesitas más que eso...

La otra opción sería poner una columna mas a GRUPOS con el atributo CANTIDAD_USUARIOS. Entonces solo tendría que actualizar ese campo cada vez que un usuario se agrega.

Eso se llama "campo calculable" y están prohibidos en las bases de datos relacionales. Se consideran un defecto grave de diseño, y sólo tienen sentido en los DataWarehouse. Un campo calculable sólo se puede usar en tablas históricas, donde a información ya no sufre NINGUNA modificación. Es información "congelada" en el tiempo.