You'd also need a TURN server if both peers are behind NAT without UPnP, which is very common. STUN alone wouldn't be enough.
From the network point of view it looks the same as two hosts starting an outgoing TCP connection through nat - if that works then hole punching should work too.
Some are trickier than others, as there are 2 IPs and 2 ports in a packet (at any point), and it can be hard to match all of them for the stricter devices, esp. on NATs that do source port randomization.
Those are called "middleboxes" (IIRC) and they're unfortunately somewhat pervasive.
You send outgoing packets simultaneously from both sides. Causing both sides to add nat translation entry’s to their nat tables. When the packets arrive both sides already have nat translation entries and the packets go right through the nat.