※cleverefについては前の記事を参照してください。
※このページの内容はここの回答とcleverefのマニュアルを参考にしました。

arXivでcleverefを使う方法

arXivはコンパイルの際に勝手にhyperrefを読み込む¹ため、cleverefを用いたコードを何も考えずに投稿すると正しく表示されません。

しかし、以下の2点を守れば正しく表示されるようになります。

\usepackage{hyperref}を\usepackage{cleveref}よりも前に、ソースコードに自ら書く。
\crefnameを用いて、\crefでの表示名を明示的に指定する。

cleverefのマニュアルに書いてあるように、(もし使うなら)hyperrefはcleverefよりも先に読み込まれなければいけません。
そのため、arXivによってcleverefよりも後にhyperrefが読み込まれないように、自ら先にhyperrefを読み込む必要があります。
また、2.に書いてある\crefによる指定は普段の環境では省略できる場合も多いため、忘れていたりそもそも知らなかったりする可能性がありますね。

poormanオプション

arXivでは上記の方法でうまく行くと思いますが、他の状況でどうしてもうまく行かない場合にはpoormanオプションを用いることでほぼ確実に解決できます。
このオプションは、cleverefを利用できないような"poor man"の環境でもコンパイルが通るようにするためのものです。

具体例と使い方を述べましょう。

hoge.tex

\documentclass{article}
\usepackage[poorman]{cleveref}
\newtheorem{theorem}{Theorem}
\crefname{theorem}{Theorem}{Theorems}
\begin{document}

\begin{theorem}
 \label{theorem:foo}
 This is a theorem.
\end{theorem}
 
 By \cref{theorem:foo}, we have ...
 
\end{document}

上記のように、cleverefにpoormanオプションを指定して読み込みます。
これをコンパイルすると、同じディレクトリにhoge.sedなるファイル²が生成されます。

sed -f hoge.sed hoge.tex > hogeforpoorman.tex

これを実行すると、次のようなファイルが生成されます。

hogeforpoorman.tex

\documentclass{article}

\newtheorem{theorem}{Theorem}

\begin{document}

\begin{theorem}
 \label{theorem:hoge}
 This is a theorem.
\end{theorem}
 
 By Theorem\nobreakspace \ref {theorem:hoge}, we have ...
 
\end{document}

確かにcleverefに依存する部分が全て取り除かれた上で、元々はcleverefによって補われていたTheoremがソースコードに挿入されていますね。
このファイルであれば、おそらくどんな環境のLaTeXでも正しくコンパイルできると思います。

(12/11 25時ごろ追記)
\crefと\Crefについて勘違いしていたことを指摘されたので、修正しておきました。
詳細は前の記事を参照してください。

00README.XXXなる名前のファイルを用いればhyperrefの読み込みを抑制できますが、何故かこの場合でも明示的に\crefnameによって設定をする必要があります。 ↩
ファイル名は元々のTeXファイルの名前で決まります。
これはhoge.texからcleveref依存の部分を全て取り去る方法が記されたテキストファイルで、terminal上で次のように入力して利用します³。 ↩
こちらで動作確認したのはubuntuのみ。macはhogeおそらくそのままで使えると思いますが、windowsは自分でsedをインストールする必要があるかもしれません。"windows sed"などでググってください。 ↩