What does the phrase "praise from Caesar" mean and where does it come from?
The full phrase is usually "Praise from Caesar is praise indeed".
The earliest I can find for the full phrase is 1903's The Smart Set: a Magazine of Cleverness, Volume 9:
The earliest I can find for the shorter phrase is 1876's Archaeologia Cantiana, Volume 10:
It is something to win praise from Caesar, and to have that praise echoed by Shakespeare, but if we may say amicus Caesar we must, as a scientific body, proclaim magis arnica Veritas, and confess that we have no trace of Caesar's ...
The next is closer to our phrase's meaning, from 1889's New Englander and Yale review: Volume 50:
This is the highest praise, and praise from Caesar, with no note of insularity.
It means someone has given you a very great compliment, typically in a situation where a compliment would be hard to earn. Caesar was the ruler of Rome and at the time one of the most powerful rulers in the world. To be complimented by him was one of the greatest honors possible, thus the current meaning.