I am a little confused here. Say you have two different domains hosted with the same hosting company (for two different sites) and therefore have the same nameservers. If you link one site to the other, will Google be able to see it? And if it sees it, will it just lower the importance of the links or penalize the site(s)?
Yes, they can see it (not necessarily nameserver only) and yes it can potentially have bad effects. I've see two heavily interlinked sites on same server/same IP (block) and they had a page each on subject X. They couldn't rank for phrase X at the same time but did get to #18 swapping spots almost daily (so never simultaneously). Judging from this I'd say they devalue 'votes for yourself' as well.
I'm no server whizz but I guess you can. However, with Google being a domain registrant and knowing all tricks of the trade, they don't base host affiliation (this is what it's called in the relevant white papers) on name servers only. A Whois record is pulled up in a fraction of a second easily. So is an IP check. Add to that that yuo might be running the same pub-id's from AdSense on each site and there's no way around it anymore. Only thing left to do is devalue it (penalize it even perhaps) from their end (my conclusions after relevant reading + experience).
Yes you can... I have multiple C block IPs on one server, but using the same name servers. If a search engine wanted to detect if certain sites were owned by the same company, I would think the best way would be to check whois info and IP or even C block IP. Because if a host's client buys a multiple site package from the host, they'll generally be hosted on the same server with the same IP. A host usually assigns C block IPs to servers, so the same C block IP could indicate the same server. Since 2 name servers can handle all of the servers combined, it wouldn't be a good way to detect ownership of the domain. So your best bet would be to have different whois info (without putting false info, since that can get your domain yanked) and different C block IPs. Different name servers is being extra paranoid, but it wouldn't hurt. All of this would mainly only count if you're doing heavy interlinking between your sites or linking all your sites to another site. just my opinion of course