If the person is not an implicit part of the image then it's debatable whether a release is necessary. It really depends on the use of a photograph, if it's being used for advertising then there's definite issues because many people stand to profit from the image, however bystanders etc in public places aren't an issue for publication in a newspaper/magazine or book.

Model release for advertising, verbal or written permission for anything else. Even then I've never used a model release, if a model's being paid and told what the images are for then it's implicit anyway there's a verbal contract, at that stage there may be an agreement that additional fees will be paid for other uses.