Nofollow links explicitly tell search engines that the links are either paid or 'not endorsed' if they give a penalty for reciprocal nofollow links they will go out of business very soon.
Interlinking as in linking to pages on your own domain, or interlinking as in linking between two websites? You should only "nofollow" internal links if they lead to content that you don't want indexed, or would be pointless for a bot trying to index, such as private user data. If you're conducting a link exchange between your website and another you should apply the "nofollow" if: 1. the website you're linking to has adult content on it, 2. the website you're linking to doesn't have the same topic of content as your website, or 3. (as jitendraag stated) if the website has paid to have a link placed on your website. Play it safe: if the link wouldn't be helpful to users, nofollow it.
Don't worry about interlinking within your own site, its a good thing. If you are worried about getting a penality for linking to too many websites, just don't link to too many and when you do only link to sites that are already in the google index and are trusted. I only use nofollow on links that go to my affiliate product ads.
Sorry I didn't specify. I mean links to other domains of mine on the same dedicated IP. There is some similarity between the sites, but it would interest somebody if they were looking for, let's say, different musical instruments. So there would be a site for guitar building, harp building, drum building, etc. Each on their own separate domain.
From the sound of it hovesh07, you've got nothing to worry about. There's no need to apply the nofollow to your links (but if you decide to you will NOT be penalized).
If you have content that you don't want indexed then using NOFOLLOW is a VERY poor method to prevent the page from being indexed. In fact it does nothing to prevent it from being indexed. Even using a rel="noindex" attribute on the link won't prevent it from being indexed if other pages or sites are linking to it without noindex/nofollow. rel="nofollow" prevents the flow of PR to the target page and for some engines prevents them from discovering the page because of that one inbound link. The best approach for to prevent content from being indexed is to use <meta name="robots" content="noindex"> or to use a robots.txt disallow for the URL. To answer the OP's question, there is no interlinking penalty for linking to someone with rel="nofollow". It is the recommended method for linking to a site that you are not willing to vouch for.