Hi,
first of all, you must configure the notification settings so the users can receive PUSH notifications when they receive a personal message.
You must do this as admin, in the Plugins -> Message output settings you will see that you can force the messaging settings for users.
Then, if you want to send the same message to all the users, you can do a bulk user action via the administration -> users menu
Regards, Juan