Why is it wrong to write: saya pikir bahwa dia perempuan??
Or you can just say 'saya kira dia perempuan'
So why does one use "dia orang perempuan" sometimes instead?
Saying "orang perempuan" is just really thorough (probably too thorough?
Is 'bahwa' needed here, or can it be left away?
Yes, it can be left away, though it would be a bit more informal.