Assume we have efficient procedures for doing mathematics in the base field F. Let F(s) be a finite field extension, where s is a root of the irreducible polynomial p(x). Elements of the extension can be represented by polynomials of s with coefficients in F. Polynomials are added, subtracted, and multiplied as usual, but every instance of sn is replaced with a linear combination of lower powers of s. This reduces the degree of the polynomial, hence it can be repeated until the polynomial has degree less than n, and is one of the elements in the field extension.
The only tricky part is division. This would be solved if we had a procedure for finding inverses. Fortunately, an efficient procedure exists for modular mathematics, based on Euclid's gcd algorithm. This procedure is easily generalized to polynomials over F, using the gcd algorithm for polynomials. I'll leave the details to you.