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][1] 
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][2], and a C version targeted at Unix and with bindings for Matlab, Octave and Python can be found 
[here][3].


  [1]: http://www.sciencedirect.com/science/article/pii/S0024379511000589
  [2]: http://www.math.mcgill.ca/drury/research/matsaev/matsaev.html
  [3]: http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/maxmod.html