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

arXivでcleverefを使う方法

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

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

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

poormanオプション

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

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

\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なるファイル²が生成されます。
これはhoge.texからcleveref依存の部分を全て取り去る方法が記されたテキストファイルで、terminal上で次のように入力して利用します³。

sed -f hoge.sed hoge.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について勘違いしていたことを指摘されたので、修正しておきました。
詳細は前の記事を参照してください。