To determine if an NFA $M$ accepts all strings , you can first convert $M$ to its construct the machine that accepts the complement language $\overline{M}$ (here is the exponential bottleneck ) $\overline{M}$. since you must first convert to a DFA). Then you can use Harry Altman's suggestion to check for emptiness.
To convert $M$ with $n$ states which accepts a language $L$ to a DFA $D$ which also accepts $L$ but using $d$ steps in poly$(n,d)$ time on a Turing machine is easy, however $d$ in the worst case is exponential in $n$ (using the naive algorithm undergrads learn). This problem is very well studied and in practice many programmes use tricks to do this more efficiently. I'm not at all familiar with these though so I cannot say if they use poly$(n)$ space and time average casethough.
