Solution 1:

For every poor soul wondering in quest for an answer to GCM background mystery. I solved it and the problem was in the format. I'm posting the right format as well as Java code needed to send Http request to GCM with some message. So the Http request should have two field in the header, namely:

Authorization:key="here goes your GCM api key"
Content-Type:application/json for JSON data type

then the message body should be a json dictionary with keys "to" and "notification". For example:

{
  "to": "gcm_token_of_the_device",
  "notification": {
    "sound": "default",
    "badge": "2",
    "title": "default",
    "body": "Test Push!"
  }
}

Here is the simple java program (using only java libraries) that sends push to a specified device, using GCM:

public class SendMessage {

    //config
    static String apiKey = ""; // Put here your API key
    static String GCM_Token = ""; // put the GCM Token you want to send to here
    static String notification = "{\"sound\":\"default\",\"badge\":\"2\",\"title\":\"default\",\"body\":\"Test Push!\"}"; // put the message you want to send here
    static String messageToSend = "{\"to\":\"" + GCM_Token + "\",\"notification\":" + notification + "}"; // Construct the message.

    public static void main(String[] args) throws IOException {
        try {

            // URL
            URL url = new URL("https://android.googleapis.com/gcm/send");

            System.out.println(messageToSend);
            // Open connection
            HttpURLConnection conn = (HttpURLConnection) url.openConnection();

            // Specify POST method
            conn.setRequestMethod("POST");

            //Set the headers
            conn.setRequestProperty("Content-Type", "application/json");
            conn.setRequestProperty("Authorization", "key=" + apiKey);
            conn.setDoOutput(true);

            //Get connection output stream
            DataOutputStream wr = new DataOutputStream(conn.getOutputStream());

            byte[] data = messageToSend.getBytes("UTF-8");
            wr.write(data);

            //Send the request and close
            wr.flush();
            wr.close();

            //Get the response
            int responseCode = conn.getResponseCode();
            System.out.println("\nSending 'POST' request to URL : " + url);
            System.out.println("Response Code : " + responseCode);

            BufferedReader in = new BufferedReader(new InputStreamReader(conn.getInputStream()));
            String inputLine;
            StringBuffer response = new StringBuffer();

            while ((inputLine = in.readLine()) != null) {
                response.append(inputLine);
            }
            in.close();

            //Print result
            System.out.println(response.toString()); //this is a good place to check for errors using the codes in http://androidcommunitydocs.com/reference/com/google/android/gcm/server/Constants.html

        } catch (MalformedURLException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Solution 2:

It is important to note that on iOS devices, if your app using GCM has been killed (swiped in the app switcher) then your device will only awake upon receiving a message if you send a notification with the "notification", "content_available" and "priority" (set to "high"). If you have one or the other, it may work when the app has been killed. But once the app has been killed, you MUST have all 3 of these keys in your notification payload.

Something like this:

{
    "to": "bk3RNwTe3H0:CI2k_HHwgIpoDKCIZvvDMExUdFQ3P1...",
    "notification": {
        "title": "test",
        "body": "my message"
    },
    "priority": "high",
    "content_available": true
}