Even native Spanish speakers make a lot of mistakes regarding the differences between deber and deber de. Both constructions are somehow close in meaning, and both govern and infinitive. Let’s have a closer look at them. Here’s a cheat sheet for you (bigger size):
deber + infinitivo
This construction involves mainly obligation, and this is the original, irreproachable use. As a rule of thumb, deber + infinitivo = “must” + infinitive; just like “must” + infinitive, it’s rather formal and could denote a moral obligation, so oftentimes people will use tener que + infinitivo = “have to” + infinitive.
Influenced by deber de + infinitivo, deber + infinitivo is now accepted for probability, supposition and assumption. This is not the original use and some grammarnazis may advice you against it, so use it at your own risk!
deber de + infinitivo
This construction accepts the probability/supposition/assumption meaning only, and should never be used for obligation, even if some natives do.
Unlike obligation deber + infinitivo, which is formal, both probability deber + infinitivo and probability deber de + infinitivo are common in regular speech, so don’t be afraid to use them.
All this theory is fine… but when the time comes…
If, when the time comes, you hesitate… always choose deber + infinitivo, which can mean everything, so you make sure you don’t make any mistake!