scrupul0us is right, this probably isn't the best project to use to start learning PHP because you're going to have to learn a large number of skills all at the same time to make this work.
To get this project working, you have two options. Learn to do it yourself (we'll try to help you a little if you are willing to do a lot of googling and reading of manuals), or you can pay someone to do it. But I can assure you, nobody here is going to write it for you.
That being said, here's the 30,000 foot view of the project.
Person #1 fills their name into a form and submits the form to Script A.
Script A checks the MySQL database to see if there are any single, unmatched people.
If yes, then redirect this person's browser to the main page and update the MySQL database to connect Joe and Dan's records to eachother not with a session ID but with a GAME Id that you pick randomly and assign to each of their two MySQL records.
If no, then redirect this user's browser to a web page that either uses Meta Refresh or Ajax to keep checking the MySQL database every 5-30 seconds to see if they've been connected to another user. This page will keep refreshing until someone else logs in and gets connected to them.
You are going to need to have a mechanism so that when person #2 logs in and sees that person #1 is looking for a game, you are going to need to find a way to make sure that person #1 is still hanging around - they might have left after three hours went by and nobody logged in to play.
Once you get the people connected, actually playing the game will rely on some of these basic principles... that is, updating records in a database and refreshing pages to see if there are updates in the database from someone else.
