Здесь я описал несколько шагов для получения RegID и уведомлений с нуля

1. Создать/Зарегистрировать приложение в Google Cloud
2. Настройка Cloud SDK с помощью разработки
3. Настроить проект для GCM
4. Получить регистрационный идентификатор устройства
5. Отправить push-уведомления
6. Получать push-уведомления

Вы можете найти полное руководство здесь:

Приступая к работе с push-уведомлениями Android: новейшая версия Google Cloud Messaging (GCM) — пошаговое руководство

Фрагмент кода для получения идентификатора регистрации (токен устройства для push-уведомлений).

Настроить проект для GCM

Обновите файл AndroidManifest

Чтобы включить GCM в нашем проекте, нам нужно добавить несколько разрешений в наш файл манифеста. Перейдите к AndroidManifest.xml и добавьте этот код: Добавить разрешения

<uses-permission android:name="android.permission.INTERNET”/>
<uses-permission android:name="android.permission.GET_ACCOUNTS" />
<uses-permission android:name="android.permission.WAKE_LOCK" />

<uses-permission android:name="android.permission.VIBRATE" />

<uses-permission android:name=“.permission.RECEIVE" />
<uses-permission android:name=“<your_package_name_here>.permission.C2D_MESSAGE" />
<permission android:name=“<your_package_name_here>.permission.C2D_MESSAGE"
        android:protectionLevel="signature" />

Добавьте объявление GCM Broadcast Receiver в тег вашего приложения:

<application
        <receiver
            android:name=".GcmBroadcastReceiver"
            android:permission="com.google.android.c2dm.permission.SEND" ]]>
            <intent-filter]]>
                <action android:name="com.google.android.c2dm.intent.RECEIVE" />
                <category android:name="" />
            </intent-filter]]>

        </receiver]]>
     
<application/>

Добавить объявление службы GCM

<application
     <service android:name=".GcmIntentService" />
<application/>

Получить идентификатор регистрации (токен устройства для push-уведомлений)

Теперь перейдите к своей активности запуска/заставки

Добавьте константы и переменные класса

private final static int PLAY_SERVICES_RESOLUTION_REQUEST = 9000;
public static final String EXTRA_MESSAGE = "message";
public static final String PROPERTY_REG_ID = "registration_id";
private static final String PROPERTY_APP_VERSION = "appVersion";
private final static String TAG = "LaunchActivity";
protected String SENDER_ID = "Your_sender_id";
private GoogleCloudMessaging gcm =null;
private String regid = null;
private Context context= null;

Обновите методы OnCreate и OnResume.

@Override
protected void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.activity_launch);
    context = getApplicationContext();
    if (checkPlayServices()) {
        gcm = GoogleCloudMessaging.getInstance(this);
        regid = getRegistrationId(context);

        if (regid.isEmpty()) {
            registerInBackground();
        } else {
            Log.d(TAG, "No valid Google Play Services APK found.");
        }
    }
}

@Override
protected void onResume() {
    super.onResume();
    checkPlayServices();
}


// # Implement GCM Required methods(Add below methods in LaunchActivity)

private boolean checkPlayServices() {
    int resultCode = GooglePlayServicesUtil.isGooglePlayServicesAvailable(this);
    if (resultCode != ConnectionResult.SUCCESS) {
        if (GooglePlayServicesUtil.isUserRecoverableError(resultCode)) {
            GooglePlayServicesUtil.getErrorDialog(resultCode, this,
                PLAY_SERVICES_RESOLUTION_REQUEST).show();
        } else {
            Log.d(TAG, "This device is not supported - Google Play Services.");
            finish();
        }
        return false;
    }
    return true;
}

private String getRegistrationId(Context context) {
    final SharedPreferences prefs = getGCMPreferences(context);
    String registrationId = prefs.getString(PROPERTY_REG_ID, "");
    if (registrationId.isEmpty()) {
        Log.d(TAG, "Registration ID not found.");
        return "";
    }
    int registeredVersion = prefs.getInt(PROPERTY_APP_VERSION, Integer.MIN_VALUE);
    int currentVersion = getAppVersion(context);
    if (registeredVersion != currentVersion) {
        Log.d(TAG, "App version changed.");
        return "";
    }
    return registrationId;
}

private SharedPreferences getGCMPreferences(Context context) {
    return getSharedPreferences(LaunchActivity.class.getSimpleName(),
        Context.MODE_PRIVATE);
}

private static int getAppVersion(Context context) {
    try {
        PackageInfo packageInfo = context.getPackageManager()
            .getPackageInfo(context.getPackageName(), 0);
        return packageInfo.versionCode;
    } catch (NameNotFoundException e) {
        throw new RuntimeException("Could not get package name: " + e);
    }
}


private void registerInBackground() {
    new AsyncTask() {
        @Override
        protected Object doInBackground(Object...params) {
            String msg = "";
            try {
                if (gcm == null) {
                    gcm = GoogleCloudMessaging.getInstance(context);
                }
                regid = gcm.register(SENDER_ID);
                Log.d(TAG, "########################################");
                Log.d(TAG, "Current Device's Registration ID is: " + msg);
            } catch (IOException ex) {
                msg = "Error :" + ex.getMessage();
            }
            return null;
        }
        protected void onPostExecute(Object result) {
            //to do here
        };
    }.execute(null, null, null);
}

Примечание: сохраните REGISTRATION_KEY, это важно для отправки сообщения PN в GCM. Также имейте в виду: этот ключ будет уникальным для всех устройств, и GCM будет отправлять Push-уведомления только REGISTRATION_KEY.

В ответ на ваш первый вопрос: да, вам нужно запустить серверное приложение для отправки сообщений, а также клиентское приложение для их получения.

В ответ на ваш второй вопрос: да, каждому приложению нужен свой ключ API. Этот ключ предназначен для вашего серверного приложения, а не для клиента.

Используйте этот код, чтобы получить идентификатор регистрации с помощью GCM

String regId = "", msg = "";

public void getRegisterationID() {

    new AsyncTask() {
        @Override
        protected Object doInBackground(Object...params) {

            String msg = "";
            try {
                if (gcm == null) {
                    gcm = GoogleCloudMessaging.getInstance(Login.this);
                }
                regId = gcm.register(YOUR_SENDER_ID);
                Log.d("in async task", regId);

                // try
                msg = "Device registered, registration ID=" + regId;

            } catch (IOException ex) {
                msg = "Error :" + ex.getMessage();
            }
            return msg;
        }
    }.execute(null, null, null);
 }

и не забудьте прописать разрешения в манифесте...
Надеюсь, это поможет!