It saves on the SD card, at least for any game I have DLC for. DLC licenses are also linked to your NNID, if you have one.
Wait, so it will technically be with my NNID as well?
A different NNID or a different 3DS completely? Because if I put that NNID on a new 3DS, would it work for free?