The type of translation you are referring to is a Dynamic PAT. This type of translation is often unidirectional. Which is to say, traffic only flows in the outbound direction. But a more accurate way of saying that is traffic only flows if it was initiated in the outbound direction.
Take a look at this illustration from this article:
Each host initiates a connection, and as each packet is translated, the translation device (in this case, the Router, but many devices can perform NAT) makes note of all the pre-translation attributes and the post-translation attributes.
Then, when the servers response, their response packets can then be matched against the translation table to un-translate the post-translation attributes back to their pre-translation attributes:
This is exactly how DNS responses (or any other responses) make it back through the unidirectional NAT translation.
As for your specific questions:
Does the NAT correlate the response to request it saw recently?
Yes. Precisely. For TCP connections, the requests stay in the translation table until the translation device sees the connection end (RST or FIN flags). For UDP connections, the requests stay in the translation table for some sort of inactivity timeout -- I often see 2 minutes, but it likely differs with each vendor.
What if multiple clients perform a different query to the same server at the same time?
The translation device assigns a unique source port for each translation so that each connection's return traffic can be uniquely identified and untranslated to the correct host.
Does it only work with upnp enabled?
Nope. Any protocol's response traffic can communicate through a Dynamic PAT using the process outlined above.
UPNP serves a different purpose. It allows a connection initiated externally to come through a Dynamic PAT, which would normally be impossible.
You can read more about UPNP here.
Disclaimer: Images and links above came from my article on Dynamic PAT on my blog. There are no ads or mandatory e-mail sign ups. The content is provided purely to help the reader and questioner.