I tried to search, but i cant find anything about:
how to compute order of curve over gf(p^m) [p>3,m>1] ?

I don't know much about ECC, but this looks like it might answer your question.

http://www.ams.org/journal-getitem?pii=S0025-5718-99-01081-9

To be honest i didnt think it can be so hard. This article looks weirdly, but i will try to understand *something*
Big thanks for your answer.

Do you know how to compute it for F_p and F_(2^n)? If you can explain these to me, then I can work out how to do the other.

The best place to ask for a real answer would be on the sci.crypt usenet group.