Your options to get free, legal songs are limited and are no different than getting them for any other device.
Both Amazon and iTunes (the two big players) will often have free songs available, but only a few. If you 'like' Apple on Facebook, you will sometimes get a coupon code for a collection of 20 or so songs. They are almost never by the same artist, but are rather a playlist essentially that you download. There will usually be a couple in each one worth keeping, sometimes all of them (very rare).
I don't use Amazon all that often so I have no idea if they do anything similar.
Past that, i can't think of many others. eMusic will give you like 50 free songs for signing up (which is also free), but their collection is mostly esoteric stuff, at least as of 2 years ago.
You can always rip your own CDs to iTunes as well. And any MP3s, WAVs, WMAs and AACs (M4As) you have will play no problem (WMAs will need to be converted first, but it shouldn't take that long on modern hardware).
Good luck with it, maybe someone else has additional suggestions. If the Nano is shiny with a camera, then it also has an FM tuner I think.