Would "mýšlím o tom divadle" be correct, too?
Přemýšlím o tom divadle. or Myslím na to divadlo.
When do you use O and when do you use Na are they the same?
No they are not the same and you have to say the preposition for each verb individually. "Myslet" uses "na".
There's no rule of when to use which and it each preposition must be learnt individually? If they are not the same what is the difference?