How does evolving a two-qubit state through a CNOT gate entangle them?

Reading into CNOT gate I understand that, mathematically, such a gate entangles the control qubit and the target. (the resulting state is $\frac{1}{\sqrt 2}(|00\rangle+|11\rangle)$)

However, looking at the "truth table" of the gate, it seems as though the result is not entangled: If I measure the target after passing the gate, the state of the control can still be either option.

Am I missing something, or did I misunderstand the truth table?

You are correct that none of the states in the truth table are entangled. Not all states become entangled when acted on by the CNOT.

The entangled state in your question would result if the control qubit was in state $|+\rangle=\frac{1}{\sqrt 2}(|0\rangle+|1\rangle)$), and the target was in state $|0\rangle$. The two qubits would then be in a superposition of $|00\rangle$ and $|10\rangle$. Apply the truth table to each of these independently, and you should see that the CNOT produces the superposition of $|00\rangle$ and $|11\rangle$ that you gave.

Note that the truth table on that page is not the only one we could write. It favours a certain interpretation of the CNOT, which is that the CNOT performs an X (the quantum version of a NOT) on the target qubit when the control is in state $|1\rangle$. An equivalent interpretation is to say that the CNOT performs a Z on the control if the target is in state $|-\rangle$ (which shows that the control and target labels are quite arbitrary). We can also interpret the CNOT as an operation that swaps the expectation values of certain Pauli operators.

The CNOT is all of these things at once. To try and explain this (and other things), I made a tutorial for quantum programming. Perhaps it will be of some use to you.

I'll try to give a slightly different perspective on the same things covered by the other answer.

A "table of truth" characterises a gate by telling you how each basis state evolves through the gate. Note that this requires choosing an input and and output bases.

In the prototypical example of the CNOT gate, one chooses the computational basis both for input and output states, and it turns out that all the elements of the computational basis evolve into other elements of the computational basis. In other words, an element of the computational basis, passing through a CNOT gate, ends up in a specific output basis state (as opposed to a superposition of basis states).

What might be confusing in this "table of truth" way to describe a gate, is that it can be used only with some choices of input and output bases. For example, you cannot give a "table of truth" description of the CNOT gate using the $$\{|L\rangle, |R\rangle\}$$ basis, because, as you can check, $$\text{CNOT}|L, L\rangle = \frac{1}{2}(|L, L\rangle + i |L, R\rangle + |R, L\rangle -i|R, R\rangle)$$. Indeed, the "table of truth representation" is only useful in some circumstances, for example when one wants to highlight that a gate might be a "quantum generalisation" of a specific classical gate, like it's the case for the CNOT gate.