In the docs nothing is told about which format should have the push sent from a server. I.e. this is not a simple standard push (like in case with iOS) - for Android all fields passed to add should be loaded into "payload" property of the "data" push message field, and the "payload" property should have "android" property inside of it with all the data to create a tray notification.
Spent several hours to find it out, CloudPush documentation should be better.
Currently I can't find this info here: http://docs.appcelerator.com/titanium/latest/#!/api/Titanium.CloudPush
or here: http://docs.appcelerator.com/titanium/latest/#!/guide/Subscribing_to_push_notifications