So we can say
"Do you think (that) he'll come?"
(in other words, we can omit THAT in conversation)
But what about with a sentence like
"Did he deny (that) he went to Thailand?"
Can "that" also be omitted like in the sentence above?
Yes, the clause subordinator "that" is optional in your examples.
Sometimes with declarative content clauses "that" is obligatory, sometimes optional, and sometimes inadmissible. Compare:
[1] That Ed is guilty is obvious. (obligatory)
[2] I know (that) it’s genuine . (optional)
[3] * I left before that he arrived (inadmissible)
In [1] the content clause is subject of the sentence and hence "that" is obligatory. In [2] “that” is optional, and in [3] it is inadmissible since “that” in a clause that is complement to a preposition like “before” is not permitted.
Elsewhere, as in [2], “that” is in general optional, though it is more likely to be omitted in informal style than in formal style, and is more likely to be omitted after short and common verbs than after longer and less frequent ones. For example, in This will demonstrate that it is genuine, the subordinator “that” would probably not be omitted.
Note: do not confuse the "that" which introduces declarative content clauses with the "that" which introduces relative clauses. They are are both subordinators, but their admissibility is subject to different constraints.
Yes, the word "that" can almost always be omitted when it is used as a pronoun to connect subordinate clauses. It's the reason that "whom" is so seldom used because often "whom" and "that" are interchangeable, although, technically "whom" is used to replace the object when it's a person and "that" is used in its stead when the object is not a person. My examples are of relative clauses unlike yours, which I have learned are slightly different; however, the same rule applies regardless:
"I'm talking to the one person in the world (whom/that) I love the most."
But
"I have read the essay (that) you have written." (never "whom" here)
Despite this rule, which would call for "whom" to be properly used in the former sentence above ("whom I love the most"), the relative pronoun "that" is often used instead, and even more often, no relative pronoun is used:
"I'm talking to the one person in the world I love the most."
"I have read the essay you have written."
To make a long story short, your sentences are fine with or without the use of "that" as it is often omitted in English sentences.
P.S. There has been much debate about what type of clause is being used in your examples above. Apparently, it's a "content clause", A.K.A., a "that-clause". I'm not going to argue with it because I haven't looked it up to see what the right metalinguistic term is for your examples specifically, nor do I care to look it up right now at 4:00AM. Just know that whether it be called a relative clause or content clause, 99% of the time the "that" can be omitted just as it was correctly done in your examples and my examples above.