Publishing Network Friends
The Publishing Network keeps track of who everyone is friends with, and friends made in one game carries over to all other games.
When you want to help your users finding other people to play with, you should first look to their Friends list.
There is also a Blocked list, and if you match up users randomly, you should check this list to make sure that users who have blocked each other never get to play with one another.
Working with the Client Libraries
Here's an example in C# of how to use the Publishing Network Friends API methods:
You can also use the Client Libraries to show various Friends-related dialogs, which will then be shown in an overlay on top of your game. This way you can get a dialog for letting the user make a friend request, or manage all of his friends, without you having to develop a UI for that in the game.