Unfortunately, it is very situational and tough to tell without seeing the sites. I tend to agree with Marcus that it generally makes me a little nervous, but Zachary is right - sitewide links aren't necessarily bad. They just tend to be associated with quality issues, especially on large scale. Still, one site is one site. Worst case, those links are probably just being devalued (in other words, Google is turning down the volume on them).
If you're sharing content across the two sites, you might want to try a cross-domain canonical tag instead. It really depends on the degree of the duplication. Still, a link bank from each piece of content to the original content is generally a good idea.
Any sitewide links, like footer links, on top of that, are probably very low value. Whether I'd remove, nofollow, or leave them alone, though, really depends a lot on the quality and the relationship between the two sites.