it's called matting, gif transparency isn't really very good, and it will always have a choppy border to some degree.
having a higher res file will help a bit, and you can also change the matt colour so that when it sits on whatever its' supposed to it blends better.
you can bring a psd into illusrator, that has full transparancy support....as do png files but they're not supported by some browsers if you plan on leaving it a transparent png for the web