Problems in algorithm2e when superscript is in text mode

When \If is exapanded, its first argument (the condition) is wrapped in an \emph{...} call such that the text occurs emphasized, i.e. usually in italics font. \text sets its argument in the current text font, which is italics in this context, so the superscript is printed like that.

As a rule of thumb, use \text in math mode only when you want to use actual explaining text. Parts of variables names shouldn't usually be mixed with text fonts. So as an alternative use \mathrm for printing the superscript. To also make the text smaller than normal superscripts, you can additionally set \scriptscriptsize, because \tiny doesn't work in math mode.

To remove code verbosity, I suggest to define new commands for those special variables:

\newcommand\xNuevo{\ensuremath{\mathbf{x}^{\scriptscriptstyle\mathrm{Nuevo}}}}
\newcommand\xMejor{\ensuremath{\mathbf{x}^{\scriptscriptstyle\mathrm{Mejor}}}}

and use them in your code:

\If{$b(\xNuevo,\mathcal{D}) < b(\xMejor,\mathcal{D})$}{...}

As for the second problem, operators in inline math mode (like between $...$) have their sub- and superscripts set next to them to reduce the height of the current line. If you want to force the scripts above and below, add \limits after the operator name:

\argmax\limits_{\mathbf{x} \in \mathcal{X}}

If you always want the scripts above/below, you can define \argmax as follows:

\newcommand\argmax{\mathop{\operatorname{arg\,max}}\limits}

Updated example:

\documentclass{article}

\usepackage{algorithm2e}
\usepackage{amsmath}
\DeclareMathOperator*{\argmin}{arg\,min}
%\DeclareMathOperator*{\argmax}{arg\,max}
\newcommand\argmax{\mathop{\operatorname{arg\,max}}\limits}

\newcommand\xNuevo{%
    \ensuremath{\mathbf{x}^{\scriptscriptstyle\mathrm{Nuevo}}}%
}
\newcommand\xMejor{%
    \ensuremath{\mathbf{x}^{\scriptscriptstyle\mathrm{Mejor}}}%
}

\begin{document}

\begin{algorithm}[H]

    \DontPrintSemicolon % Some LaTeX compilers require you to use \dontprintsemicolon instead

    \KwIn{.}
    \KwOut{.}
    %   \textit{Inicialización}:\\
    %   Aleatoriamente inicializar $b_{u}$ y $b_{i}$\\

    \For{$t = 1$ \text{hasta} $T$}{

        Ajustar $\Psi$ hasta $\mathcal{H}$\\ 
        $\mathbf{x}^{\text{\tiny Nuevo}} = \argmax\limits_{\mathbf{x} \in \mathcal{X}} a(\Psi(\mathbf{x},\mathcal{D}), \mathcal{H})$\\
        Evaluar $b(\mathbf{x}^{\text{\tiny Nuevo}},\mathcal{D})$\\

        \If{$b(\xNuevo,\mathcal{D}) < b(\xMejor,\mathcal{D})$}{


            $\mathbf{x}^{\text{\tiny Mejor}}=\mathbf{x}^{\text{\tiny Nuevo}}$\\
            $\mathcal{H} = \mathcal{H} \cup (\mathbf{x}^{\text{\tiny Nuevo}},b(\mathbf{x}^{\text{\tiny Nuevo}},\mathcal{D})) $


        }

    }

\Return $\mathbf{x}^{\text{\tiny Mejor}}$

\end{algorithm}

\end{document}