FindMinimum[{9.0 n (m - 1.0)^4 + (m n - 2.0)^2, -1.0 <= m <= 4.0 && -1.0 <= n <= 4.0}, {m, n}]
gives your answer.
{-693., {m → 4., n → -1.}}
Your subject title has been edited to be more informative.
Minimize[{9 n (m - 1)^4 + (m n - 2)^2, -1 <= m <= 4 && -1 <= n <= 4}, {m, n}, Integers]
seems to give the answer you seek.
{-693, {m -> 4, n -> -1}}
As mentioned in the documentation, NMinimize only guarantees a global minimum value only if the cost function and its constraint are linear. You may need to try different functions and also plot the reuslt to help you find the global miminum. Another function you can try is:
FindMinValue[{9.0 n (m - 1.0)^4 + (m n - 2.0)^2, -1.0 <= m <= 4.0 && -1.0 <= n <= 4.0}, {m, n}]
Just to reemphasize something from above:
Mathematica supports both exact numbers and approximate numbers (with finite numerical precision - aka floating point numbers):
http://reference.wolfram.com/mathematica/tutorial/ExactAndApproximateResults.html
Essentially, a floating point number is a bit different than the kind of numbers that you learn about in a math class.
When using a symbolic function like Minimize, it is best to use exact numbers only. Using approximate numbers may result in unexpected numerical issues since symbolic functions may not be as numerically stable as numerical functions.
In your specific case, simply switching to exact numbers gets you the answer that you expect. Note that all I have done is removed all the decimal points - in Mathematica, approximate numbers have decimal points while exact numbers do not:
In[28]:= Minimize[{9 n (m - 1)^4 + (m n - 2)^2, -1 <= m <= 4 && -1 <=
n <= 4}, {m, n}]
Out[28]= {-693, {m -> 4, n -> -1}}
The explanation for the poor result from your Minimize run is that when Minimize is given
approximate numbers (floating-point), it switches to NMinimize which handles floating-point
numbers better. NMinimize is less clever about dealing with local minima. When Minimize
is given an equation and constraints that use only exact (Integer or Rational) numbers,
it can use more mathematical techniques.
In[1]:= Minimize[{9.0 n (m - 1.0)^4 + (m n - 2.0)^2, -1.0 <= m <= 4.0 && -1.0 <= n <= 4.0}, {m, n}]
Out[1]= {-143., {m -> -1., n -> -1.}}
In[2]:= Minimize[{9 n (m - 1)^4 + (m n - 2)^2, -1 <= m <= 4 && -1 <= n <= 4}, {m, n}, Integers]
Out[2]= {-693, {m -> 4, n -> -1}}
@Bruce, I think you would like to say “NMinimize is less clever about dealing with global minima” 
I think that the issue is that NMinimize is more likely to get “stuck” in a local minimum and never get to the global one. So it is less clever with local minima.