This is basically a web design question - not just a "theme" question. I've been running my own web design business for several years now, and there are some basic rules to what you're asking.
First off, it's a personal preference on these questions. If you "don't feel right" doing one thing over another, then don't do it - it's totally up to you. However, the legalities of them (I am not a lawyer, nor do I play one on TV - but I know this much from my own contracts and speaking with my own lawyer on the subject):
1) I do. Simply because I need the linkback - it's part of my marketing straegy for my business. I usually put it somewhere *very* small, and it blends in with the theme so that it doesn't stand out - except for people who are looking for it. But as a designer who wants to gain more clients, it's in my contract that a link back to me is required from the index page. I need that for SEO purposes and to promote my business, and to gain more clients. To any clients in the past who have wanted that removed (which, actually, I've never had anyone ask!), then they need to pay an fee for having it removed - every good, solid link back to me helps to promote my business - so if they don't want it, they are doing something detrimental to my business and therefore, must pay a few to have it removed. Granted, it's not a huge fee, but it makes the client aware of exactly how important that link back to me is.
2) Unless you have signed a piece of that transfers all of your copyrights to your work and design to the person you have designed the layout for, then you can do whatever you want with it. Copyright is NEVER given to anyone (in the United States, anyway - I don't know where you are!) without a signed document from the originator of the piece. For example, when I do sites for clients, in my contract, I state they own the RIGHTS to use the design for a certain period of time - usually 2 years. That means they exclusively have that design for 2 years, but the copyright is mine. They can't touch the code, they can't alter the design, they can't play with the images on the site - the only thing they can alter is the content. After the 2 years is up, I can most assuredly sell that same design to another company if I so desire. Now, if the client wants copyright to the design and layout so they can do whatever they want to it, they *do* pay a nice, large fee for the joy of explicity owning the copyright to my hard work. I've yet to have a client actually pay that fee - because for *those* rights, you are asking a lot, and you will shell out a lot for them.
In my years of practice in the web design field, this is pretty much standard for your work. And keep in mind that if you use stock imagery or someone else's work, those items don't fall under your rights to the copyright - as the originator holds copyright (you can't give away copyright for someone else!) only the stuff *you* create does.
Hope that helps you out!