Reconciling NP and the decision problem
By definition, all NP-complete problems are decision problems. In fact, the category of NP-completeness only applies to decision problems. Any other kind of problem cannot be NP-complete any more than an apple.

A decision problem A is in NP if there is an integer $m$ and a decision problem B, which can be decided in polynomial time, such that:


If $x \in A$ then there exists $y$ of size at most $m|x|^m$ (here $|x|$ is the size of $x$ in bits) such that $\langle x,y \rangle \in B$.
If $x \notin A$ then for every $y$ of size at most $m|x|^m$ it holds that $\langle x,y \rangle \notin B$.


The string $y$ is called a witness.

This definition is a bit abstract, so let me explain it using your example, the Max Cut problem. The Max Cut problem, as a set, consists of all pairs $\langle G,k \rangle$ such that $G$ is a graph containing a cut which cuts at least $k$ edges. The desired witness $y$ is a cut which cuts at least $k$ edges. The decision problem B consists of all pairs $\langle \langle G,k \rangle, C \rangle$ in which $G$ is a graph and $C$ is a cut in $G$ which cuts at least $k$ edges. The problem Q can be decided in polynomial time – that is, given a graph $G$, a cut $C$ in $G$, and an integer $k$, it is easy to check whether $C$ cuts at least $k$ edges. The size of $C$ is also polynomial in the size of $\langle G,k \rangle$.

As jmite explains in the other answer, this definition is equivalent to the more usual one: NP consists of all decision problems which can be decided using non-deterministic polynomial time machines. Let me sketch why the two definitions are equivalent.

Suppose first that A is in NP according to the definition stated above. The non-deterministic polynomial time machine deciding A guesses the witness $y$ and then verifies it (using the polynomial time algorithm for B), accepting if the verification succeeded.

For the other direction, the sequence of non-deterministic choices functions as the witness $y$. We can verify that a specific sequence leads to acceptance by running the non-deterministic polynomial time machine using $y$ as its choices.