As Pieter pointed out, the correct way to define argmin and argmax operators in LaTeX is:

\usepackage{amsmath}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

Actually, using the amsopn package would be sufficient but it's loaded by amsmath internally, which is recommended for math typesetting anyway.

The * in \DeclareMathOperator* places the underscored argument underneath the word rather than to the bottom right of it.

Summary

In the sequel, LaTeX is assumed.

Preliminary questions

1. Should a thin space separate “arg” from “min”?

This is a matter of personal preference. The default definition for \limsup has a thin space, on the other hand “arcsin” is usually written without a space between the two components. Consistency is, as always, the keyword: using a macro definition will ensure it and also easiness in modifying the typesetting in the whole document, if switching from one option to another is needed.

2. Should limits go below the operator in display style?

Also this is debatable and conventions used in the field the document is written for should be followed.

3. Should the operator name be typeset upright?

Definitely, like all other operator/function names such as sine and cosine.

Available tools

1. amsmath

With amsmath one can do, in the preamble,

\DeclareMathOperator*{\argmin}{arg\,min} % thin space, limits underneath in displays
\DeclareMathOperator*{\argmin}{argmin} % no space, limits underneath in displays
\DeclareMathOperator{\argmin}{arg\,min} % thin space, limits on side in displays
\DeclareMathOperator{\argmin}{argmin} % no space, limits on side in displays

Of course, only one of these should be used. In the document it's sufficient to type \argmin and the spacing around the operator will be the right one according to the common rules of math typesetting.

The seemingly different

\newcommand{\argmin}{\operatornamewithlimits{argmin}}

is not really so, because it's essentially the same as \DeclareMathOperator*{\argmin}{argmin}; moreover it uses a deprecated command, that should be \operatorname*.

2. No package

The following definitions are very similar to the ones above, in the same order

\newcommand{\argmin}{\mathop{\mathrm{arg\,min}}
\newcommand{\argmin}{\mathop{\mathrm{argmin}}
\newcommand{\argmin}{\mathop{\mathrm{arg\,min}\nolimits}
\newcommand{\argmin}{\mathop{\mathrm{argmin}\nolimits}

With \underset

\underset{x}{\mathrm{argmin}}

This also was mentioned in the question and in one answer, but it is wrong, as the visual comparison will show.

3. Differences

The “no package” version is much more rigid than the amsmath version, because this package can receive the nonamelimits option that will automatically change all operators such as \lim, \max that usually have limits underneath (in displays) to have them on the side. The same option would of course act also on newly defined operators, provided \DeclareMathOperator* has been used.

Test document

In the following test document, the proposed definitions or constructions will be compared.

\documentclass{article}
\usepackage{amsmath}

% limits underneath
\DeclareMathOperator*{\argminA}{arg\,min} % Jan Hlavacek
\DeclareMathOperator*{\argminB}{argmin}   % Jan Hlavacek
\DeclareMathOperator*{\argminC}{\arg\min}   % rbp

\newcommand{\argminD}{\arg\!\min} % AlfC

\newcommand{\argminE}{\mathop{\mathrm{argmin}}}          % ASdeL
\newcommand{\argminF}{\mathop{\mathrm{argmin}}\limits}   % ASdeL

% limits on side
\DeclareMathOperator{\argminG}{arg\,min} % Jan Hlavacek
\DeclareMathOperator{\argminH}{argmin}   % Jan Hlavacek
\newcommand{\argminI}{\mathop{\mathrm{argmin}}\nolimits} % ASdeL

\newcommand{\cs}[1]{\texttt{\symbol{`\\}#1}}

\begin{document}

\begin{align}
&\cs{argminA}  & \argminA_x f(x) &= \{x \mid f(x) = \min_{x'} f(x')\} \\
&\cs{argminB}  & \argminB_x f(x) &= \{x \mid f(x) = \min_{x'} f(x')\} \\
&\cs{argminC}  & \argminC_x f(x) &= \{x \mid f(x) = \min_{x'} f(x')\} \\
&\cs{argminD}  & \argminD_x f(x) &= \{x \mid f(x) = \min_{x'} f(x')\} \\
&\cs{argminE}  & \argminE_x f(x) &= \{x \mid f(x) = \min_{x'} f(x')\} \\
&\cs{argminF}  & \argminF_x f(x) &= \{x \mid f(x) = \min_{x'} f(x')\} \\
&\cs{underset} & \underset{x}{\mathrm{argmin}} f(x) &= \{x \mid f(x) = \min_{x'} f(x')\}\\
&\cs{argminG}  & \argminG_x f(x) &= \{x \mid f(x) = \min_{x'} f(x')\} \\
&\cs{argminH}  & \argminH_x f(x) &= \{x \mid f(x) = \min_{x'} f(x')\} \\
&\cs{argminI}  & \argminI_x f(x) &= \{x \mid f(x) = \min_{x'} f(x')\}
\end{align}

\end{document}

Results

As predicted, many lines typeset the same. However, the macros defined with \mathop will not obey the nonamelimits option. Also the result of \argminD is clearly wrong, as the limit is typeset below “max” and not below the whole operator name.

The construction with \underset is wrong because it will not use the correct spacing after the operator: a thin space follows all others and it is the right way to typeset. Compare \sin x and \mathrm{sin}x to see this thin space in a different context.

Note that \argminC and \argminA give the same result, as well as \argminD and \argminB. Explanation: \arg and \max are already defined as operators, so TeX inserts a thin space if one directly follows another one. Using \argminC or \argminD just makes TeX spin its wheels a little more, with no advantage over \argminA or \argminB.

Use \usepackage{amsmath} and then:

\operatorname*{argmin}_\theta f(x)

Or similarly (for adding a space),

\operatorname*{arg\,max}_\theta f(x)

I use \newcommand{\argmin}{\operatornamewithlimits{argmin}}.

Just another alternative (in some sense the poorer solution around, see comment below), could be to define \argmin in terms of \min and \arg commands.

\newcommand{\argmin}{\arg\!\min}

In this way, 1) \argmin will behave always the same way as \min, 2) doesn't need amsmath or care about \operator... commands 3) yes, the variable in not centered (it is centered in the min part), but that may even be what you want (since it is centered in the same ways a \min, also the 'g' in \arg doesn't further lower the under-argument).

\documentclass[fleqn]{article}
\newcommand{\argmin}{\arg\!\min}
\begin{document}

\[ \argmin_x f(x) = \{x | f(x) = \min_{x'} f(x')\} \]
\[ \min_x f(x) = \{f(x) | f(x) < f(x_0) \forall x_0 \in R \]

\end{document}

Using \underset does not require any other package. An above answer says:

With \underset

This also was mentioned in the question and in one answer, but it is wrong, as the visual comparison will show.

If the only thing "wrong" is that there is no space between the argmax and the f(x), then just add \, (thin space) to fix the problem:

z = \underset{x}{\mathrm{argmax}}f(x)

z = \underset{x}{\mathrm{argmax}}\, f(x)

or you could use the underset command. For example:

    R = \underset{n} {\mathrm{argmax}} ~P(L_n|\mathbf{x})

I would use \mathop and \mathrm, and eventually \limits or \nolimits, depending on the desired behavior when combined with _ and ^. See below.

\documentclass{article}

\begin{document}

{
nothing:
\newcommand{\argmin}{\mathop{\mathrm{argmin}}}
$\argmin_a^b$
$$\argmin_a^b$$
}

{
limits:
\newcommand{\argmin}{\mathop{\mathrm{argmin}}\limits}
$\argmin_a^b$
$$\argmin_a^b$$
}

{
nolimits:
\newcommand{\argmin}{\mathop{\mathrm{argmin}}\nolimits}
$\argmin_a^b$
$$\argmin_a^b$$
}

\end{document}

This works without any additional package. However it will create a new line.

$$\pi(s) = arg\max_\theta$$