There are various algorithms that output the eigenvalues of an $n \times n$ matrix in time $O(n^3)$. However, I can't find anywhere that tells me about the precision of the output of the algorithm. That is, what is the time complexity of increasing the number of bits I require the answer to?
Furthermore, how does this rely on the number of bits we use to specify the initial matrix? For example, if I specify the matrix elements to exponential precision in $n$.
Any starting point for this would be helpful.
I do not have a complete answer to your question but here are some thoughts and references. First of all, it is crucial to specify the model of computation and the representation of the input, I expect this post will clarify why. I know of essentially two cases:
Based on your question, I suspect your matrix has rational inputs (which are algebraic numbers of degree 1), thus it would fit in the first case. In this case, I think (but have not checked) that the bit complexity will be linear (maybe with polylogarithmic factors) in the precision, but the constant will depend on the size and numbers in the input matrix (most probably in a polynomial fashion).
(*) algebraic numbers can be represented exactly with a finite number of bits, all arithmetic operations (and more) on algebraic numbers can be performed effectively, however the complexity details on the height of the numbers, thus on field extension in which the coefficients of the input lie.
 Optimal and nearly optimal algorithms for approximating polynomial zeros, Pan, 1996
 Complexity Theory of Real Functions, Ko
 A Computable Spectral Theorem, Brattka and Ziegler
 The Complexity of the Matrix Eigenproblem, Pan and Chen