I wanted to submit one of my themes to the new wordpress.org directory, but it says that themes submitted there have to be General Public License competible. Now, what exactly does it mean? does it mean anyone will be able to replace a header in my themes, change a few colors and release them as their own, without having to give credits, ask for permission, etc? Thanks in advance!
AFAIK, people would be able to modify and release it, but will have to give due credit to you. http://www.gnu.org/philosophy/license-list.html#GPLCompatibleLicenses
Most wordpress themes require that you keep the footer link intact. A backlink in the footer is much much better than a name drop in the css.
A requirement like that would not be GPL - you are allowed to do whatever you want including removing stuff as long as you credit and make your changes available.
Most themes aren't under the GPL, they are under the Creative Commons Commercial Attribution license, which requires that you leave the footer link intact. You should check on the specific license for your theme, because it really depends on that.
That's true in an overall sense, but in the wordpress.org directory, all themes must be GPL compatible.