Given a compact manifold $M$ with a handle decomposition, a chain complex can be formed where the chain groups are freely generated by the handles in each dimension and the boundary maps are given by $$ \partial_k(h_\alpha^k) = \sum < h_\alpha^k | h_\beta^{k-1}> h_\beta^{k-1} $$ where the coefficients $<h_\alpha^k | h_\beta^{k-1}>$ are the intersection of the attaching sphere of $h_\alpha^k$ with the belt sphere of $h_\beta^{k-1}$.
My confusion is with how we compute these intersection numbers. I know that the two spheres will just intersect in points and so we just need to count the points with sign. How do we get the sign? Does it suffice to orient $M$ right of the bat (assuming that we can do that)?
You do not need to orient $M$, in fact $M$ may not be orientable so this may be impossible.
However, you do need to orient the boundary of each handle before you start computing the intersection numbers. And this is possible because the boundary of each handle is simply a sphere of dimension one less than the dimension of $M$. I'll add that you also need to orient the belt of each handle, and you need to orient the attaching sphere of each handle.
For example, suppose $M$ is a three dimensional manifold. A 1-handle can be expressed as $[-1,+1] \times D^2$ and its boundary sphere is $([-1,+1] \times S^1) \cup (\{-1,+1\} \times D^2)$ which is homeomorphic to the 2-sphere, and you'll need to choose an orientation of this 2-sphere. Once that is chosen, by restriction you get an orientation of the annulus $[-1,+1] \times S^1$ (you could probably get away with just choosing an orientation of this annulus).
Also, the "belt" of the 1-handle is the circle $0 \times S^1$, which is the core of the annulus $[-1,+1] \times S^1$, and you'll need to choose an orientation of this belt.
When a 2-handle is attached to the union of $0$-handles and $1$-handles, the attaching sphere of that 2-handle is a circle, and you'll need to choose an orientation of that circle.
Now you are all set up to make sense of the boundary formula in your question: each time the attaching sphere of the 2-handle crosses the belt $0 \times S^1$ in the annulus $[-1,+1] \times S^1$, you have all the orientations you need in order to define the intersection number.