Both android devices are considered clients. The clients will communicate with a backend server which can be implemented in a variety of ways. The sample that Google provides uses a standard web app written for the Java App Engine. You can find the example here:
Setting Up the Server
You can also write the server using ASP.NET, PHP, etc. What I typically will have on the backend is also a SQL database to manage the devices that are registered with my application. Each device (client) is given a unique ID from Google which the server will use to communicate. The server uses this ID because the messages it will send is not directly to the client but to GCM service. So in essence the Google GCM is a server to your backend server which is a client to GCM.
Hopefully this answers your questions regarding client/server communication. Please look at Googles demo for detailed implementation. Good luck!