An ear will appear only if the one with the perk is credited with the kill. For example, firing a missile at the car behind the target and killing him with the subsequent explosion will not count. Similarly, any death blows landed by followers results in no ear appearing. A kill by the Mysterious Stranger will not yield an ear, either.
While you cannot kill essential characters, an ear will spawn in their inventory each time they are knocked unconscious. These can then be pick-pocketed from them.
The most abundant supply of ears you can find are off of Regulators which are encountered randomly through having negative Karma.
Slaver-hunting hitmen are also a good supplier of ears as well, should the player also choose to be a slaver.