It is certainly sufficient to always calculate the full $2^n\times 2^n$ unitary matrix, and then apply it to the $2^n$-entry state vector. If that's what you choose to do, that's all you have to do as all the entanglement information is contained in that vector. A quick and easy way to see if a particular qubit is entangled is to take the partial trace of your (pure) state vector over all other qubits. If the resulting matrix is rank 1, that qubit is in a separable state, otherwise it's entangled.
I assume the point of your question is really "How can this huge computational cost be avoided?". In general, it can't - if you're making use of the full power of the quantum computer, you will always need the $2^n$-entry state vector. However, there are various tricks that reduce the computational cost, such as delaying the need for such a large state vector by keeping track of the entanglement.
Efficiency Improvements
The biggest saving that you can make compared to the naive implementation above is to avoid the $2^n\times 2^n$ unitary matrices. For example, if you are only using 1- or 2-qubit gates, simply using the sparsity of matrices means you only need $O(2^n)$ storage instead of $O(2^{2n})$.
Then there are other tactics that you can employ. For example, imagine you want to apply the two-qubit unitary gate $U$ on qubits $i$ and $j$. You can take sets of 4 elements from your state vector ($|x\rangle_{1,2,\ldots n\setminus i,j}|y\rangle_{i,j}$ for fixed $x\in\{0,1\}^{n-2}$ by taking all different $y\in\{0,1\}^2$) and just applying the $4\times 4$ unitary $U$ on that 4-element vector. Repeating this for every $x$ will return $U$ enacted on the original state vector.
I imagine there are other strategies one could come up with. The one that suggested itself from the original question was entanglement tracking. This gives memory and speed improvements at the start of a computation, but ultimately ends up being equivalent because (presumably) everything in the quantum computer will end up entangled.
Entanglement Tracking
Let's assume that your computation consists of only unitary evolution and measurement on the set of $n$ qubits, i.e. there is no decoherence, probabilistic maps etc. Let's further assume that you start from a fully separable state such as $|0\rangle^{\otimes n}$. At this point, every qubit is separable, and it is sufficient to keep $n$ different registers, each conveying the state of a separable qubit. If your first gate is just a single-qubit operation $U$ on qubit $i$, then you just update the state stored on qubit $i$ as $|\psi_i\rangle\mapsto U|\psi_i\rangle$, and you don't have to touch anything else.
If you want to do a two-qubit gate $V$ between qubits $i$ and $j$, say, then you have to combine the states at both sites. So, you replace two registers each of dimension 2 with one register of dimension 4, containing state $V|\psi_i\rangle|\psi_j\rangle$. The problem is that you now can't split this state up again, so you have to keep those two qubits in a register forever after. Of course, if you ever have a 1-qubit gate $U$ to apply on qubit $i$, you'll now have to apply $|\psi_{i,j}\rangle\mapsto U\otimes\mathbb{I}|\psi_{i,j}\rangle$. Then, the next time you want a 2-qubit gate between, say, $j$ and $k$, you'll have to combine the spaces for $(i,j)$ and $k$. Those spaces will keep growing, but if a gate is localised on just one space, you only have to apply it there (using $\mathbb{I}$ operators to pad it on the rest of the qubits), and you don't have to do anything to the other spaces.
If you're doing things like this, you will not have (at least for the first few steps of your algorithm) a single $2^n$ element register. You'll have to have a bunch of different registers, and keep track of which qubits are described by which register in a separate array. Each time you combine the spaces of some qubits, you'll update that extra array.
Here's some very crude pseudo-code that may help to convey my meaning:
#initialise variables
entangled_blocks={{1},{2},{3},...,{n}}
quantum_states={{1,0},{1,0},...,{1,0}}
#apply action of each gate
for each gate
for each gate_target
target_block=entangled_blocks entry containing gate_target
next gate_target
if all target_blocks equal then
apply gate on target_block (pad with identity on other qubits)
else
new_entangled_block=union(target_blocks)
new_state_vec=tensor_product(quantum_states for each target block)
apply gate on new_state_vec (pad with identity on other qubits)
replace all target_blocks in entangled_blocks with new_entangled_block
replace all quantum_states(all target blocks) with new_state_vec
end if
next gate
Other Options
(By no means exhaustive)
You may be interested to read about Matrix Product States which are a nice way of encapsulating the information about not-too entangled states, and that may provide an alternative route for you, depending on exactly what it is that you're trying to achieve.
