S.W. Drury derives a method to find the operator norm of a general real matrix $$ A : \ell^p \longrightarrow \ell^q $$ in a recent paper in Lin. Alg. Appl (and using it, refutes a long-standing conjecture of Matsaev).
In keeping with the answer of Alex Olshevsky, the algorithm seems have a complexity exponential in the number of columns of the matrix (but linear in the number of rows).
Drury's implementation for Visual C++ and Maple can be found here, and a C version targeted at Unix and with bindings for Matlab, Octave and Python can be found here.