In the software Regina what I do is apply [Descartes Rule of Signs][1] on the characteristic polynomial.  The algorithm for computing the determinant we use has complexity of the order of $n^4$, but it seems to work quite effectively for the signature computations we've been doing so far. 

  [1]: http://en.wikipedia.org/wiki/Descartes%2527_rule_of_signs

The primary reason we use these techniques is they're fairly easy to implement.  Also, we're worried about rigour so we want to avoid floating-point data types that could have round-off errors.  We use arbitrary precision integers for the computations, via the GNU Multi-Precision libraries.