PHP, MySQL: How to get the user's first and last name

$sql = "SELECT (user.forename, user.surname, other_fields...)
          FROM conversation
    INNER JOIN conversation_member
            ON conversation.conversation_id = conversation_member.conversation_id
    INNER JOIN conversation_message
            ON conversation.conversation_id = conversation_message.conversation_id
    INNER JOIN users_table /* replace this with the name of your user table */ AS user
            ON user.user_id = conversation_member.user_id
         WHERE user.user_id = :userid
           AND conversation_member.conversation_deleted = 0
      GROUP BY conversation.conversation_id;"

$query = $db->prepare($sql);
$query->bindParam(':userid', $userid, PDO::PARAM_INT);
$query->execute();
$results = $query->fetchAll();
$user = $results[0]["user"]; //stores array of user fields (forename, surname, etc)

SELECT
   c.conversation_id,
   c.conversation_subject,
   user.firstname,
   user.lastname,
   MAX(cmes.message_date) AS conversation_last_reply, 
FROM conversation c, conversation_member cmem, conversation_message cmes, user_tablename user
WHERE c.conversation_id = cmes.conversation_id
AND c.conversation_id = cmem.conversation_id                          
AND cmem.user_id = {$_SESSION['user_id']}
AND cmem.conversation_deleted = 0
AND user.user_id_column = whatever.you_used_as_foriegn_key
GROUP BY c.conversation_id
ORDER BY conversation_last_reply DESC

Assuming the columns names are like that

You need to join with the "conversation_member" table again, this time, selecting the other user's id where the same conversation_id and message_id applies:

SELECT
    c.conversation_id,
    c.conversation_subject, 
    MAX(cmes.message_date) AS conversation_last_reply,
    cmem2.user_id AS other_user_id
    CONCAT(usr_tbl.firstname, ' ', usr_tbl.lastname) AS other_user_name
FROM conversation c
    JOIN conversation_member cmem
    JOIN conversation_message cmes
    JOIN conversation_member cmem2
    JOIN users_table usr_tbl

ON  c.conversation_id = cmes.conversation_id 
AND c.conversation_id = cmem.conversation_id                          
AND cmem.user_id = {$_SESSION['user_id']}
AND cmem.conversation_deleted = 0

AND c.conversation_id = cmem2.conversation_id                          
AND cmem2.user_id = {$_SESSION['other_user_id']}
AND cmem2.conversation_deleted = 0

GROUP BY c.conversation_id
ORDER BY conversation_last_reply DESC

I don't see why you're having trouble getting the user's first and last name if you were able to construct the rest of that query by yourself?

Try something along the lines of, :

SELECT cmem.user_id, u.first_name,  u.last_name, c.conversation_id, c.conversation_subject, MAX(cmes.message_date) AS conversation_last_reply  
FROM conversation c  
INNER JOIN conversation_member cmem on c.conversation_id=cmem.conversation_id  
INNER JOIN conversation_message cmes on c.conversation_id=cmes.conversation_id  
INNER JOIN users u on u.user_id = cmem.user_id
WHERE cmem.user_id = {$_SESSION['user_id']} AND cmem.conversation_deleted = 0  
GROUP BY cmem.user_id, u.first_name, u.last_name, c.conversation_id, c.conversation_subject

Now, I think you should also be reconsidering your database structure so that all these joins are not necessary. I see several problems. One, your database seems to be over-normalized. Why do you have a separate "Conversations" table that has only two fields, conversation id and subject? In any message system I've ever seen, the subject is always visible so you would always have to join the conversation table just to get the subject field. The conversation_id is in every other table anyway. Just add the subject field to the message table and eliminate the conversation table if that's all it's holding, normalization isn't always a good thing.

Second, why do you set a flag for deleted messages instead of just deleting them? I've also never seen a message system that lets me restore messages I've deleted. At the very least, if you want to retain them for whatever reason you should move them to an archive table so that the primary table you're running selects off of doesn't have to deal with the performance hit of parsing through meaningless "deleted" entries.

Lastly, what is the conversation_member table anyway? Based on my interpretation, it's supposed to represent a member of the conversation since it has a user_id. Why would the conversation delete flag be present for a single member of a conversation? If anything it should be in the conversation table. With that improvement, the only field left in it is conversation_last_view, which really no one cares about. The more important thing is conversation_last_post, which can be easily derived from the timestamp of the last message posted in the thread.

Ultimately, if you just want to see the first and last names appended to your query it's as simple as joining the users table and displaying those two entries. The SQL query I provided should get you close if it doesn't work straight out, I'm too lazy to copy your database and try it myself. However, I think you should really consider the overall design of your database as well so you don't run into needless performance issues down the road.

To answer the question of: Finding all users in a conversation, MINUS the current user:

    SELECT (users.forename, users.surname)
      FROM conversation_members AS members
INNER JOIN users_table AS users
        ON members.user_id = users.user_id
     WHERE members.conversation_id = :conversationid
       AND NOT users.user_id = :userid

Where :userid is the current user and :conversationid is the conversation in question.