This is something I've been interested in lately. I haven't found detailed information, but I'll share the basics.
I found an article here. The most important trait, from what I've read, is the ability to focus without becoming distracted:
When selecting a dog of any age, selecting one with a HIGH level of
ball/play drive is necessary. You want a dog that is focused and
intense about playing.
Breed doesn't seem too important, so long as it's a fairly intelligent breed. To begin SAR training, a dog needs to already have basic obedience training. It's hard to find more information without getting in contact with a group that offers the training.
I briefly volunteered with the SES (an Australian emergency service), and at the time they were looking for volunteers who had dogs who would be interested in training their dogs. I get the impression that trainers and handlers are often the same person, and it's an on-going process to maintain the required level of training for both handler and dog.
EDIT: Oh, I forgot, a dog that's anxious around people will have a hard time working in search and rescue.