My programming friends are always telling me that HTML is a markup language and C++ is a programming language. When I ask them what's the difference, they never give me a reasonable answer.

What could make one call C++ a programming language, and HTML not?

A programming language is a notation designed to pass instructions to a machine. By that definition both C++ and HTML are programming languages, as was the notation Joseph Marie Jacquard used in 1801 to program his looms.

However with the proliferation of languages that are used to structure and/or describe data, the definition of a programming language shifted to include only languages that are capable of expressing algorithms. This is the more common definition today and it excludes languages like HTML or XML. 

At the heart of the current definition is the concept of Turing completeness. Most programming languages are Turing complete, and Turing completeness is often quoted as the one critical trait that separates a programming language from any other computer language. This is good enough as a general rule of thumb, but not entirely accurate:


Some non Turing complete languages are considered programming languages, for example Charity.
Some languages that are not generally considered programming languages are Turing complete, for example XSLT.
Turing completeness alone doesn't say much about a language's usefulness. 


Depending on context, you can pick any definition you want. 

Edit:

Let it further be known, an implementation of a language does not confer characteristics onto the language itself, for example: A language's spec may define a turing complete language, someone could implement it haphazardly leaving off turing completeness. This implementation being non-turing complete does not however mean the language itself is not turing complete (rather it likely means that implementation is non-conformant). The details of a language and the details of a particular implementation of a language are to be recognized as separate things, this is why it's inaccurate to call a language interpreted or compiled etc.
