How does Playlist sharing work? I have many playlists synced from my Mac to my iPhone and recently I 'shared' one of these playlists with a friend via the share card on my iPhone (sent to his phone via iMessage).

To my surprise he was able to listen to all the songs on the playlist, even songs that I know aren't available on iTunes (so only available on my Mac). I'd like to know how this feature works.

FYI both of us have Apple Music.
I'm not sure how fully this will answer your question, but in the absence of something official from Apple it's probably the best guess there is.

Essentially, when one subscribes to Apple Music and also activates the iCloud Music Library, iTunes effectively syncs what's in your library with what's on Apple's servers. Music you have which is not available on iTunes is actually uploaded so that the servers have a way of sharing that music across your devices.

Typically users can share their playlists with other users and, assuming they're both subscribed to Apple Music, there is no issue with this as both subscriptions have access to the music already available on Apple's servers.

Now, what's happened in your case according to your question is that even songs that I know aren't available on iTunes (so only available on my Mac) were accessible by your friend who was able to listen to them all. This isn't surprising if the songs in question are already available on Apple's servers separately, but you're implying that they're not usually available, and that's where things get a little murky. 

I have personally manually imported music into my iTunes library (on my Mac) which as far as I could tell were not available on Apple's servers. However, some of them do get synced and are then available on all my devices, while others never become available to any of my devices (outside my Mac). What I can't account for is what differentiates these songs? 

For example, I may search for ten songs on Apple's servers which do not come up on any search results. I then manually add them to my iTunes library and the whole syncing process (by virtue of the iCloud Music Library) takes place. Why it is some of them become available to my other devices, and some are not, I cannot say. However, the ones which are not available are still listed in the playlists on all my devices, even though they cannot be played (outside of my Mac). Trying to play them on other devices results in a "Item Not Available: This item can't be played" message.

If I check on iTunes (on my Mac) these songs have the symbol that represents either Waiting or Not Uploaded (they have the same icon - see here). So while they can be played on my Mac, they're not available on my other devices because they weren't able to be matched or uploaded (and therefore they cannot be shared with others as well). Sometimes these resolve over time, sometimes they just seem to stay that way.

While it would be easy to assume this is some sort of bug, I think it's more likely that if a song which is not usually available on Apple's servers is nevertheless matched, the servers are then able to discern if the track can be played or not (because of some other licensing agreements, etc). However, if the song cannot be matched (which could just mean they weren't uploaded), then they can't be shared.

In a nutshell, the very act of having Apple Music and also iCloud Music Library activated means that all your songs, even the ones not normally available on Apple's servers, are synced to iCloud (even if it means having to actually upload them). This then makes them available (rightly or not) to other subscribers with whom you may share your playlists.