How are databases able to process queries in parallel while still retaining correct order?
Answers relevant to SQL Server.  

If talking about query priority:  

For SQL Server there is by default a FIFO principle adhered to. The first query to run gets priority.
However with the resource governor it is possible to not only limit the resources assigned to your sql server instances, it is also possible to create workload groups which can prioritize certain connections to be able to run before others. 

If talking about parallelism:

For SQL Server it does this by running parallel streams, that are fed information by a parallel page supplier, and in their turn have their information fed through a gather streams operator into a stream aggregate operator, which gathers the information provided by the separate streams to then be passed on further.

In other words, for SQL Server this is done by gathering the processed data at the end, and bundling it a new. If needed they can then be sorted or filtered afterwards.

See this simple talk article for more details.