tcolorbox: \newtcbtheorem referencing

Since tcolorbox version 2.41 (2013/07/23), there is integrated support for the cleveref package. You just have to move \crefname and \Crefname as options into \newtcbtheorem:

\documentclass{article}
\usepackage[most]{tcolorbox}
\tcbuselibrary{theorems}
\usepackage{cleveref}
\newtcbtheorem[auto counter, number within = section,
  crefname={example}{Example},
  Crefname={Example}{Example} ]
{Example}{Exam\smash{p}le}{%
  breakable,
  fonttitle = \bfseries,
  colframe = blue!75!black,
  colback = blue!10
}{exa}
\begin{document}
\begin{Example}{Example}{exam}
  Some example
\end{Example}
\noindent
\Cref{exa:exam} and~\cref{exa:exam}.
\end{document}

The output is identical to that of the solution of Gonzalo Medina.

You need to define the format for the new object; in this case, for tcb@cnt@Example, using something like

\crefformat{tcb@cnt@Example}{example~#2#1#3}
\Crefformat{tcb@cnt@Example}{Example~#2#1#3}

or any other format you want. A complete example:

\documentclass{article}
\usepackage[most]{tcolorbox}
\usepackage{cleveref}

\makeatletter
\crefformat{tcb@cnt@Example}{example~#2#1#3}
\Crefformat{tcb@cnt@Example}{Example~#2#1#3}
\makeatother
\newtcbtheorem[auto counter, number within = section]
{Example}{Exam\smash{p}le}{%                                                        
  breakable,
  fonttitle = \bfseries,
  colframe = blue!75!black,
  colback = blue!10
}{exa}
\begin{document}
\begin{Example}{Example}{exam}
  Some example
\end{Example}
\noindent
\Cref{exa:exam} and~\cref{exa:exam}

\end{document}

The correct name to be used in \Crefformat, and \crefformat can be obtained from one of the warnings obtained in the original code using \Cref without the proper definitions:

LaTeX Warning: Cref reference format for label type `tcb@cnt@Example' undefined on input line 21.

As of 2020-09-08, the previous offered solutions do not work anymore. The cleveref 4.31 (2020-07-31) documentation provides an example and solution to this problem on page 372: the label type optional argument is used to feed cleveref with the needed name information.

MWE:

\documentclass{article}
\usepackage{tcolorbox}
\tcbuselibrary{theorems}
\usepackage{cleveref}

\newtcbtheorem{example}{Example}{label type=example}{exa}

\begin{document}

\begin{example}{title}{label}
Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
\end{example}
Checking if \textbf{cleveref} works: \cref{exa:label} and \Cref{exa:label}.

\end{document}