But they are vague about the implications and I'm generally unsure about the practical relevance of quantum protocols like superdense coding ...
Other quantum protocols are much more likely to be useful, perhaps particularly for cryptography.
Both of these require spending entanglement, so it’s not a very useful heuristic.
How do you do this?
(it goes against my intuition of a qubit as state in a hilbert space)
The Bell basis measurement has four outcomes. For convenience you can label them
00 01 10 11
Alice tells Bob the measurement outcome she got (this is the part that requires two bits of classical communication), and depending on which outcome she got Bob has to apply either no correction or a Pauli X, Y or Z gate.
This is known as quantum teleportation
https://en.wikipedia.org/wiki/Quantum_teleportation
and has quite a long history at this point (proposed in the early '90s and first performed in the late '90s).
Yes one needs entanglement.
https://qiskit.org/textbook/ch-algorithms/teleportation.html