This is something I still don't seem to understand. When do I use each of these options?

For example when the pre-condition of an interface is not met. Apparently this is the optimal place to use an exception, but I don't see the point of it. Let's say I'm working on an interface and in that interface, the pre-condition of function B is that function A must be executed before B. So if I throw an exception, how can I trust that something out in the other side of the interface catches it? Especially considering that the rest of the program is not made by me as I'm only doing the interface and its implementation. Since calling B before A is illegal, what should I actually do? Call an assert?

As always, you can choose.

However, that doesn't mean there are better options. An assert is very good for debugging purposes - though it crashes the program and gives you information, on release builds (with NDEBUG defined) it completely disappears.

Even so, its a bit heavy-handed, and on release builds will give you no error reporting at all. In that case, often exceptions are a good idea. Of course, they should be used as the 'exception' to the rule. So, if A must be called before B, an exception is a good thing to put in B to check. Either the above code catches it and fixes something, or it lets it go through and the exception behaves a bit like an assert.

Of course, its never a good thing to just let B keep going, because if it needs A to be in a valid state than otherwise you have some weird things going on. So an exception or a premature return is the best thing.

Nevertheless, its all down to personal opinion. No one is telling you to use exceptions - they are just sometimes a good tool for the job.

So would it be bad practice to just check the condition in the beginning, give a debug message and return the function prematurely? The situation where B gets called before A is something that only happens in the actual programming phase and if it happens, the program crashes anyway (B modifies information that A has needs to initialize). It's something that can never happen during the actual run time, given that the program works as intended, so I don't really see the point of exceptions in this case.

Should I use exceptions, who would catch the exception? It seems kinda counter-intuitive to have the caller catch an exception after the caller has made an illegal function call. Or is this exactly how it should be done (or rather, recommended)?

First, let's look at the situations where exceptions are supposed to be thrown:
1. Failure to establish a postcondition. For example, a function or an operator returns an object by value, but it has no valid value to return. Extreme case of this are the constructors: they always throw exceptions on errors, which interact with a few more language features resulting in RAII.
2. Failure to re-establish a class invariant (only applies to non-private member functions). It's normal for a member function to temporarily break an invariant, but it has to guarantee to put it back before returning.
3. Failure to satisfy the preconditions of some other functions that has to be called.

Those are errors, errors for which exceptions exist. The program cannot continue and has to roll back (or quit)

What you're talking about are contracts: wide-contract functions accept every input, but throw exceptions if they don't like it (e.g. vector::at). They bear the cost of always checking the input, even though in the expected usage the check is supposed to be pretty much always redundant.
Narrow-contract functions have preconditions: the behavior is only defined for a subset of all possible inputs (e.g. vector::operator[] and pretty much every C library function. Narrow contract functions typically have asserts for debug builds.

Note that some precondition checks may be so costly, they would render the function useless, like calling is_sorted to check if binary_search may proceed. There is nothing wrong with debug-only asserts.