If they are following the page and the notification are not turned off, then yes, they will get notified the instant you create a live video. Usually, the notification is sent out immediately, but there might be a delay for larger pages.