How come RTOSs are considered deterministic?
As far as RTOSs are concerned (on an embedded system), when we write a
  multithreading application, I think the same thing happens depending
  on how many threads are executing concurrently.


NOPE!

If that happens, then it isn't a REAL-TIME OS (RTOS). 

The short-answer is that the definition of an RTOS has nothing to do with multi-tasking or priority. It is simply that all tasks have timing guarantees. 

The rest of what you consider to be characteristics of an RTOS (prioritization, task completion, etc) are merely consequences (or features) of building a system where tasks must finish within the specified time interval. 

Multi-tasking in an RTOS is conceptually simpler than in a soft-time OS as many of the complicating edge-cases are essentially not allowed.