1) You would put the nofollow attribute after the href part normally, but it probably doesn’t matter either way.
2) Nofollow won’t harm an affiliate link, it simply tells the search engines that you don’t endorse the link. Users don’t see nofollow, so they still click and get to where they want to go. Some programs don’t want you to modify their code, but adding nofollow to simple hyperlink will still work just fine.
3) According to the search engines you should use nofollow when you don’t want to endorse an external site, but you still want to have the link on your site. Nofollow was invented to combat blog spam for the comments portion where everyone was posting spammy links. Having nofollow means that Google and others will just ignore remove any of the juice that would normally pass to that website.
4) Potentially, there are many reasons why your website may be penalised. Linking out to a bunch of spammy sites is definitely one way to get a penalty. Start by going to Webmaster Central on Google to figure out if/why your site has a penalty.