There can be a number of issues that are happening here. I'll try to cover them all as best I can. First, I'm based on your description, it sounds as though it's safe to assume you have Tasks enabled in Salesforce1.
Notifications also need to be enabled in Salesforce1 in Setup > Administer > Mobile Appications > Notifications > Salesforce1. You'll see a dialogue that looks like the one below.
At a minimum the 1st item needs to be checked if you want notification to be sent to Salesforce1. If you want Users to be able to allow them to be "pushed" to Salesforce1, then you also need to check the 2nd one that I've outlined in red.
Its important to be aware that checking the 2nd box doesn't mean it will happen, as the choice will still be up to the user whether to enable push notifications in Salesforce1 on their mobile device.
Related to this is a setting in Customize > Activities > Activity Settings as shown below:
If the box outlined in red is checked, individual users can control whether and how they’re notified when someone assigns them a task. This could affect whether they receive notifications in Salesforce1.
In a user's advanced profile settings, you'll see a link to their mobile push registrations as outlined in red in the image below.
In the Salesforce1 App, these are configured in the Setting dialogue as shown below. The first item in the menu is Push Notification Settings as outlined in red.
Once you're in the Push Notification Settings you'll want to checkmark the box for "Someone assigns you a task" as outlined in red below.
The screen captures of Salesforce1 shown above are from the Android Version 10.0. Under Android (and I assume iOS too), although you may have enabled these settings, there are numerous ways to disable notifications from any app using system overrides from the OS whether intentional or not. This can easily happen unintentionally if you're using a Battery Saver/Power App.