What's the difference between a CTE and a Temp Table? What is the difference between a Common Table Expression (CTE) and a temp table? And when should I use one over the other?

CTE

WITH cte (Column1, Column2, Column3)
AS
(
    SELECT Column1, Column2, Column3
    FROM SomeTable
)

SELECT * FROM cte


Temp Table

SELECT Column1, Column2, Column3
INTO #tmpTable
FROM SomeTable

SELECT * FROM #tmpTable
This is pretty broad, but I'll give you as general an answer as I can.

CTEs...  


Are unindexable (but can use existing indexes on referenced objects)
Cannot have constraints
Are essentially disposable VIEWs
Persist only until the next query is run
Can be recursive
Do not have dedicated stats (rely on stats on the underlying objects)


#Temp Tables...  


Are real materialized tables that exist in tempdb
Can be indexed
Can have constraints
Persist for the life of the current CONNECTION
Can be referenced by other queries or subprocedures
Have dedicated stats generated by the engine


As far as when to use each, they have very different use cases.  If you will have a very large result set, or need to refer to it more than once, put it in a #temp table.  If it needs to be recursive, is disposable, or is just to simplify something logically, a CTE is preferred.

Also, a CTE should never be used for performance.  You will almost never speed things up by using a CTE, because, again, it's just a disposable view.  You can do some neat things with them but speeding up a query isn't really one of them.