I would like to know when to say think(s) that, say(s) that and mean(s) that and when to omit that.
In most cases, if any of these verbs is followed by an embedded clause, that is completely optional.
are both completely grammatical, and normal in speech. The form with that is probably slightly more formal, so you're more likely to encounter it in writing than in speech; but both occur in both speech and writing.
There is a lot of scholarly literature on the subject of "that-deletion", for example this paper, which says "It has implicitly been assumed in the literature that the language arbitrarily allows sentence-embedding predicates, such as the ones in (1), to embed their sentential complements with or without the complementizer that".
But the paper does give some cases where that may not be deleted, such as
where, apparently because of the intervening prepositional phrase, that is required (at least for most speakers).
So, in short, with these particular verbs, you are never wrong to include that, but in ordinary speech or informal writing, as long as the clause comes straight after the verb you may omit it.