Cada mensaje de GCM admite hasta 1000 destinatarios, vamos, que no hace falta enviar 1000 mensajes iguales pero sí saber los identificadores de todos.
Evidentemente, si tienes más de 1000 usuarios es cuestión de crear un mensaje nuevo por cada mil usuarios.
Cómo lo implementes ya depende de cómo gestiones los usuarios registrados en la base de datos.