See http://www.gnutellaforums.com/showthread.php?t=49851 about the deletion of files. You'd need a file recovery utility. Restoration is supposed to be very good considering it's free. But whatever you do, don't recover the files to the same partition as those that were deleted or you will greatly minimise chances of recovery. And don't save any other files there either until you've finished recovering.

As for adding songs to iTunes/iPod see how to do it properly How to transfer music to my iPod (& iTunes). I'd recommend manual updating of the iPod.