Should all team members be formally trained when introducing Agile methods into a company, or is it sufficient to train only a handful of key people? If the latter, who should they be?
As others have mentioned, train the whole team. It is hugely valuable to build a common language and common perspective early on for any process transition. Agile especially can be a cultural level change that takes months (12-18) to change everyone's core behaviors. It isn't as simple as learn the ABC's of a process.
Also, train Sr. Management. I can't stress this enough. Having a single team in a company "go Agile" will create tension and conflict that needs to be managed by Sr. Managers. If they don't know what to expect or aren't prepared, it will create problems almost immediately ("well, you can do Agile, but Product Management will keep working the way they always have...") You can't send them to the same class, so I would strongly recommend a trainer come in and spend 2-4 hours speaking to a significant portion of the Sr. Mgmt team and tailoring a course specifically for them.
Also also, find a few sympathetic/interested/motivated members of other groups/teams and get them trained as well. Once you get some success with your team, having those seeds planted early will really help solidify things.
You definitely want to train all team members. You could potentially do a "train the trainer" type setup where a few key individuals get trained and then train the rest of the team, but your results will be much better if everyone gets trained. You will also probably want to at least give overview training to anyone else that typically interacts with the team so they are familiar with the changes as well.
Our agile adoption process was doing alright before we brought in an external coach, but once we brought in an external coach to formally train and coach the entire team and provide overview training to others that typically worked with the team, the team really took off. It made a world of difference just taking that time to get everyone on the same page, and having the outside perspective as well.
I found one company with about 80 devs who trained themselves after sending five of their members to a Scrum Master course. They got themselves to the point where they were releasing code to production several times a day, and several teams had started using Kanban instead to be able to visualise the flow more easily.
I went to see them because I was curious about how they did this. It turned out they had the right culture in place; particularly, an academic, open-minded culture in which they were more interested in trying things out and working out what failed than in blaming people for the failure. They were also self-motivated, and the company made time for learning, so they were willing to pick up books, read blogs and go to groups in the evenings to ask questions.
If you can find people who have enough influence (not authority!) to create a culture in which Agile can thrive, it's enough to train those people, provided they're given training on the principles as well as on the practices.
Otherwise, provide training or coaching for everyone.
If you are starting from scratch then I think external training for all is a good idea. You definitely want to have your training just-in-time and learners should be with the people they will be working with so I would advise training one team at a time.
Expecting a few key people to pass the word on may be risky. Internal trainers have superior context but there are some intangibles to having an external trainer. External trainers will usually be more accomplished facilitators and presenters. External trainers will have experienced many different patterns that they can share with learners. For whatever reason, learners always extend external people more courtesy and this can be valuable in the early stages of the learning curve - there are some who learn through challenging and questioning and this can throw an inexperienced trainer off-balance.
Good luck Iain