What is a notification server, and what does it serve?

In general terminology, a server is a program that clients connect to in some way (whether over network or over local IPC mechanisms). The notification server is therefore a program that accepts "show a notification" requests from clients, and shows notifications on their behalf.

What is a notification client, and what does it do?

Any program that uses a notification server becomes a "notification client". This is again not a notification-specific term; it's about the general architecture.

What is this notify-send think I can use to make a notification pop up? Is it the (well, a) client?

Yes, it's a client in this case. Its purpose is mostly just so that you can make notifications pop up; apps don't run it because they can perform the same operations directly in their own process.

What is a notification daemon?

Exactly the same thing as a notification server.

The term 'daemon' has a somewhat different meaning; it refers to any kind of background service, whether it is a "server" or not – but in this case, the program that's responsible for showing the actual notification popups is both a server and a daemon at the same time (as it runs in background like a daemon, and accepts requests like a service).

And what is the role of libnotify?

It's a small library that can be used by notification clients, to abstract away the specifics of the IPC mechanism being used (as well as the differences between protocol versions). Instead of needing to know about D-Bus and interfaces, the program just does notify_notification_new(...).

(That said, many apps choose to implement the communications directly, e.g. using libdbus to make the necessary calls – it's a pretty simple protocol so both options are probably equally common.)

The protocol that's used between a client (like libnotify) and a notification server is also often misnamed "the libnotify protocol".

And from the perspecitve of the user (me), is the difference between those two aesthetic? I mean, when one is running vs the other is running, I see that the notification looks different

That is literally the difference. The idea is that each desktop environment (GNOME, KDE, etc.) would have its own notification server that would show popups tailored for that desktop environment.

Incidentally, here comes the question "what are they serving?", because it looks to me that they are only waiting for some other tool to send them notifications, so that they can show them in a nice way.

Yes, but "waiting for some other tool to send them notifications" is what counts as "serving" something. A service doesn't necessarily have to return some data as a result – there are plenty of services in any system that are more-or-less one-way, i.e. whose job is to do something rather than to return something.

Anyway, what if I want to do custom stuff with the notifications? Say that I want to get them all and have my own shell script that, say, just appends them in a file ~/notifications. Would that mean I'm writing my own notification server? Or client? Or what?

You would be writing your own "notification server" if it implements the notification protocol, i.e. the agreed-upon method by which clients communicate with it. For most Linux systems, the de facto standard is implementing the "org.freedesktop.Notifications" interface through D-Bus – if you implement it, you have a notification server.

(Though it will be really difficult to do that through a shell script, but it can be done in about 10 lines of Python or Perl, given that the interface consists of approximately two functions.)

I've tried with notification-daemon first. This doesn't work just upon installing it. For a call to notify-send to be successful, one has to either launch it (it means executing /usr/lib/notification-daemon-1.0/notification-daemon) manually, autostart it somehow, or create a file at /usr/share/dbus-1/services/org.freedesktop.Notifications.service with this content

[D-BUS Service]
Name=org.freedesktop.Notifications
Exec=/usr/lib/notification-daemon-1.0/notification-daemon

The absence of this file is deliberate, because it implies that there is only one program providing this specific service – while in reality one may have multiple desktop environments installed, each having its own notification service, and D-Bus has no mechanism to prioritize one implementation or the other.

So while many other D-Bus services are autostartable, most notification servers deliberately aren't, so that they wouldn't be chosen to be started in the "wrong" desktop environment. The desktop environment is meant to "manually" start the appropriate service, e.g. you might start it from your ~/.xinitrc if that's what you do.

Then I tried dunst, but that, as soon as installed, just works, in the sense that notify-send just works. I think this is fundamentally because it starts itself upon the first call to notify-send (which means that I initally had the impression that it worked also after I had uninstalled it; that's because the dunst process was running), but how does it do that?

It uses the exact same method that you described above – its package actually includes a D-Bus .service file:

$ cat /usr/share/dbus-1/services/org.knopwob.dunst.service

[D-BUS Service]
Name=org.freedesktop.Notifications
Exec=/usr/bin/dunst
SystemdService=dunst.service

The only difference is that the actual file is not named after the service it supposedly provides (dbus-daemon doesn't enforce this requirement for "user" services).

I've also given a look at statnot which seems very very skinny and without frills, but with reference to the my previous paragraph, it feels like using statnot would still mean that I would still have to write a configuration that, via the function update_text, calls into some API that xmobar or xmonad exposes. This way I would not have control on, say, how many notifications I want to show at a time.

That seems to be unavoidable. If you want custom logic, then you need to write custom logic.

For example, I had once written a notification daemon that uses dzen2 as the "popup". You can implement any logic you like in the Notify() method.